Linear layouts of weakly triangulated graphs
Bibliographic record
Abstract
A graph [Formula: see text] is said to be triangulated if it has no chordless cycles of length 4 or more. Such a graph is said to be rigid if, for a valid assignment of edge lengths, it has a unique linear layout and non-rigid otherwise. Damaschke [Point placement on the line by distance data, Discrete Appl. Math. 127(1) (2003) 53–62] showed how to compute all linear layouts of a triangulated graph, for a valid assignment of lengths to the edges of [Formula: see text]. In this paper, we extend this result to weakly triangulated graphs, resolving an open problem. A weakly triangulated graph can be constructively characterized by a peripheral ordering of its edges. The main contribution of this paper is to exploit such an edge order to identify the rigid and non-rigid components of [Formula: see text]. We first show that a weakly triangulated graph without articulation points has at most [Formula: see text] different linear layouts, where [Formula: see text] is the number of quadrilaterals (4-cycles) in [Formula: see text]. When [Formula: see text] has articulation points, the number of linear layouts is at most [Formula: see text], where [Formula: see text] is the number of nodes in the block tree of [Formula: see text] and [Formula: see text] is the total number of quadrilaterals over all the blocks. Finally, we propose an algorithm for computing a peripheral edge order of [Formula: see text] by exploiting an interesting connection between this problem and the problem of identifying a two-pair in [Formula: see text]. Using an [Formula: see text] time solution for the latter problem, we propose an [Formula: see text] time algorithm for computing its peripheral edge order, where [Formula: see text] and [Formula: see text] are respectively the number of edges and vertices of [Formula: see text]. For sparse graphs, the time complexity can be improved to [Formula: see text], using the concept of handles [R. B. Hayward, J. P. Spinrad and R. Sritharan, Improved algorithms for weakly chordal graphs, ACM Trans. Algorithms 3(2) (2007) 19pp].
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.000 | 0.003 |
| Meta-epidemiology (narrow) | 0.001 | 0.001 |
| Meta-epidemiology (broad) | 0.000 | 0.001 |
| Bibliometrics | 0.002 | 0.001 |
| Science and technology studies | 0.001 | 0.001 |
| Scholarly communication | 0.001 | 0.002 |
| Open science | 0.001 | 0.002 |
| Research integrity | 0.001 | 0.001 |
| Insufficient payload (model declined to judge) | 0.007 | 0.002 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".