Bibliographic record
Abstract
The study of planar graphs dates back to Euler and the earliest days of graph theory. Centuries later came the proofs by Wagner, Fary and Stein that every planar graph can be drawn with straight line segments for the edges, and the algorithm by Tutte for constructing such straight-line drawings given in his 1963 paper, “How to Draw a Graph”. With more recent attention to complexity issues, this was followed in 1990 by algorithms that construct such drawings on a small grid. Most people think of “morphing” as a brand new concept, and in fact, the word “morph” was coined in the 80’s as a short form of “metamorphose”. In common perception, morphing is a high-tech special effect in movies, where, for example, a person’s face turns smoothly into a cat’s face. We use the term in a more mathematical sense: a morph from one drawing of a planar graph to another is a continuous transformation from the first drawing to the second that maintains planarity. Mirroring the developments in planar graphs, the first result was an existence result: between any two planar straight-line graph drawings there exists a morph in which every intermediate drawing is straightline planar. This was proved surprisingly long ago for triangulations, by Cairns in 1944, and extended to planar graphs by Thomassen in 1983. Both proofs are constructive—they work by repeatedly contracting one vertex to another. Unfortunately, they use an exponential number of steps, and are horrible for visualization purposes since the graph contracts to a triangle and then re-emerges. The next development was an algorithm to morph between any two planar straight-line drawings, given by Floater and Gotsman in 1999 for triangulations, and extended to planar graphs by Gotsman and Surazhsky in 2001. The morphs are not given by means of explicit vertex trajectories, but rather by means of “snapshots” of the graph at any intermediate time t. By choosing sufficiently many values of t, they give good visual results, but there is no proof that polynomially many steps suffice. Furthermore, the morph suffers from the same drawbacks as Tutte’s original planar graph drawing algorithm in that there is no nice bound on the size of the grid needed for the drawings. For the case of drawing planar graphs the issue of grid ∗David R. Cheriton School of Computer Science, University of Waterloo, alubiw@cs.uwaterloo.ca size was addressed in 1990 independently by Schnyder and by de Fraysseix, Pach and Pollack, who gave algorithms to construct a straight line planar drawing of any n-vertex planar graph on a grid of size O(n)×O(n). The history of morphing planar graph drawings has not progressed to this stage. It is an open problem to find a polynomial size morph between two given drawings
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.001 | 0.005 |
| Meta-epidemiology (narrow) | 0.001 | 0.001 |
| Meta-epidemiology (broad) | 0.001 | 0.001 |
| Bibliometrics | 0.002 | 0.002 |
| Science and technology studies | 0.001 | 0.001 |
| Scholarly communication | 0.002 | 0.004 |
| Open science | 0.001 | 0.003 |
| Research integrity | 0.001 | 0.002 |
| Insufficient payload (model declined to judge) | 0.027 | 0.006 |
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".