Balanced Schnyder woods for planar triangulations: an experimental study with applications to graph drawing and graph separators

Luca Castelli Aleardi

REVIEW 3 major objections 5 minor 28 references

Balanced Schnyder woods for planar triangulations: an experimental study with applications to graph drawing and graph separators

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A balance heuristic for Schnyder woods improves planar drawings and separators

desk verdict A careful, well-scoped experimental study of a new balance heuristic for Schnyder woods; the causal claim about balance itself is plausible but not isolated from confounds. read the letter →

arxiv 1908.06688 v1 pith:ZNXAXNY4 submitted 2019-08-19 cs.DS cs.DMmath.CO

Luca Castelli Aleardi This is my paper · ORCID

classification cs.DScs.DMmath.CO

keywords Schnyderwoodsplanartriangulationsgraphdrawingcycleseparatorslinear-timeheuristicbalancedorientationsexperimentalalgorithmsmeshregularity

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that simple linear-time heuristic choices inside a standard vertex shelling can produce Schnyder woods whose three color classes are balanced at each vertex. Experiments across real-world meshes, random triangulations, and synthetic regular grids suggest these balanced woods make Schnyder drawings more regular—fewer long edges and flat triangles—and provide short, balanced cycle separators. The practical payoff is speed: the heuristic processes over a million vertices per second, and once the drawing exists, a separator is read off almost instantly. No worst-case guarantee is claimed; the contribution is empirical evidence that exploiting regularity in real inputs works.

What carries the argument

The load-bearing mechanism is a priority-based vertex conquest. The standard shelling maintains a boundary cycle and repeatedly removes a free vertex, assigning colors and orientations to its incident edges; the heuristic gives each boundary vertex a priority equal to the number of incoming edges already assigned to it, stores vertices in a small number of queues by priority, and always removes the highest-priority free vertex. This retards vertices with few incoming edges, so they accumulate edges of several colors before being removed, which is what keeps defects small. A post-processing reversal of oriented triangles can further raise the fraction of balanced vertices on regular graphs, at extra cost.

What would settle it

Take a single near-regular triangulation with about a million vertices, run the balanced heuristic over many random seeds, and compare the worst-case separator boundary and drawing edge-length metric to a minimal Schnyder wood; if the worst balanced result is no better than the minimal one, the claim that balance drives quality is falsified.

Watch

Extended reading notes

Core claim

A Schnyder wood is an edge coloring and orientation of a rooted planar triangulation in which every inner vertex has one outgoing edge of each of three colors; the paper measures its balance by a defect $\delta(v)$, the spread between the most- and least-frequent incoming colors (with a small correction when the degree is not divisible by 3). The central discovery is that retarding the removal of vertices that have accumulated few incoming edges during the incremental shelling produces woods in which most vertices are balanced, and that this balance is strongly associated with drawing quality and separator quality. On a fixed seed, the paper generates a sequence of woods from balanced to unbalanced by randomly reversing oriented triangles, and both the edge-length layout metric and separator boundary size worsen as the average defect increases.

Load-bearing premise

The measured correlation between balance and quality is causal, and the tested triangulations are representative enough to generalize the in-practice claim.

Editorial extensions

If this is right

On regular meshes, a large majority of vertices become balanced (about 79% for a spherical grid-type graph), whereas minimal Schnyder woods leave most vertices with large defect.
Schnyder drawings obtained from balanced woods have higher edge-length uniformity and capture regular structure; unbalanced woods show long edges and flat triangles.
Cycle separators extracted from balanced woods have boundary sizes well below the $\sqrt{8m}$ bound on most tested graphs, often close to $\sqrt{m}$, with balanced partitions meeting the $2/3$ ratio.
Separator extraction after the drawing is computed is near-instantaneous (about 0.01 seconds for graphs with around a million vertices).
The choice of initial seed has limited effect on balance, but for high-diameter graphs it can materially change separator length.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

I infer the likely mechanism behind the empirical correlation: balanced woods spread the three color classes evenly around each vertex, preventing the long spiraling paths that both stretch edges and inflate separator boundaries; this suggests the same balancing should help other Schnyder-wood applications such as compact encodings and spanners.
A natural testable extension is to apply the priority rule to non-triangulated planar graphs (after a preprocessing triangulation) or to higher-genus maps, and check whether balance still predicts layout and separator quality.
To separate balance from other shelling effects, one could run a control that perturbates the shelling order while keeping priority structure fixed; if quality does not track the defect, the causal claim would need revision.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper is worth a serious look: it defines a balance measure for Schnyder woods, gives a simple linear-time priority-queue shelling heuristic, and runs the first broad experimental evaluation across real meshes, random triangulations, Delaunay, and synthetic grids. The code and data are available, timings are solid, and the claims are carefully hedged. That is real work, and it is honest work.

What is actually new: the balance objective itself, the retarded conquest heuristic, and the experimental comparison against minimal Schnyder woods for drawing quality and cycle separators. The results on regular meshes are convincing that the heuristic produces more balanced woods (up to 79% balanced vertices on the sphere), and the paper does not try to sell theoretical guarantees it does not have. The runtime comparison with previous separator implementations is also fair and favorable.

The soft spots are real but not fatal. The Fig. 3 experiment is the main one: starting from a heuristic wood and randomly reversing ccw triangles changes not just δavg but the full orientation pattern, path lengths, winding, and the number/location of ccw faces. The monotone trend therefore does not establish that balance per se causes the quality improvement; the shelling order or other correlated structural changes could be doing the work. The paper never acknowledges this confound, and the heuristic's priority is based on incoming-edge counts rather than δ directly, which makes the connection between its objective and the measured metric indirect. On top of that, there are no significance tests, and the separator baseline is essentially just Fox-Epstein et al., so the state-of-the-art comparison is incomplete.

But these are addressable issues, not load-bearing flaws. The central claim—that balanced Schnyder woods are a practical preprocessing step for drawing and separating mesh-like graphs—is plausible and supported by the comparison against minimal woods, even if the isolated causal role of balance is not proven. A control experiment that perturbs balance while holding other structure fixed would strengthen the paper considerably, and the author should be asked to add one.

The paper is for researchers in graph drawing and experimental algorithms who work with planar triangulations. It deserves a serious referee, not a desk reject, and I would recommend conditional acceptance after the causal evidence is improved.

Referee Report

3 major / 5 minor

Summary. The paper studies balanced Schnyder woods for planar triangulations. It defines a vertex defect measure δ(v), global balance metrics δ0 and δavg, and proposes a linear-time heuristic based on a retarded vertex-conquest shelling procedure with k priority queues, optionally followed by a post-processing phase that reverses oriented triangles. The heuristic is used in two applications: Schnyder straight-line drawings, evaluated by the edge-length aesthetic metric, and simple cycle separators, evaluated by boundary size and partition balance. The experiments cover real-world meshes (aim@shape, Thingi10k), synthetic grids, random planar triangulations, and Delaunay triangulations, with hundreds of random seeds. The paper explicitly disclaims theoretical guarantees and claims only empirical evidence that balanced Schnyder woods improve layout quality and separator quality compared with minimal Schnyder woods.

Significance. If the empirical claim is correct, the paper offers a cheap and practical preprocessing step for two well-studied problems: higher-quality Schnyder drawings and short balanced cycle separators. The paper's strengths are the breadth of its test suite, the repetition over hundreds of seeds, the availability of datasets and code, and the honest framing that no worst-case guarantees are provided. The balance metric is computed independently of the heuristic's objective, and the separator selection scans all vertices, so there is no obvious fitting-to-target circularity. However, the causal link between balance and quality is not yet established: the experiment intended to isolate balance is confounded, and the comparisons lack statistical support. The contribution is therefore plausible and useful, but it needs strengthening before the abstract's causal wording is justified.

major comments (3)

[Section 2.3, Fig. 3] The experiment designed to isolate the effect of balance is confounded. Starting from a heuristic balanced wood and randomly reversing ccw-oriented triangles changes not only δavg but also the full orientation pattern, the three paths P_i(v) used by the drawing and separator routines, the number and location of ccw faces, and the region sizes Int(R_i(v)) on which separator balance is evaluated. Consequently, the monotone relationships in the middle and right charts of Fig. 3 could be driven by these correlated structural changes rather than by the balance defect itself. To support the paper's central claim, the manuscript should include a control that varies balance while holding other structural features roughly fixed (for example, comparing heuristic and minimal woods with matched δavg values, or performing a regression that includes path-length and ccw-face counts as covariates), or it should explicitly weaken the abstract's causal wording to a correlation statement.
[Section 2.3, Figs. 1, 3, 4, 6, 7] The main empirical claims are reported without statistical tests or effect-size measures. The paper states conclusions such as "our heuristic leads to well balanced Schnyder woods" and "the layout quality tends to deteriorate" based on whisker plots, but no confidence intervals, standard errors, sample sizes per graph, or paired tests (e.g., Wilcoxon signed-rank over seeds) are given. Because the entire contribution is an empirical improvement claim, the authors should quantify the significance and magnitude of the differences between heuristic and minimal woods for balance, layout, and separator size.
[Section 2.3, Fig. 4] The separator results are summarized with aggregate charts and a few per-graph labels, but the reader cannot determine how many seeds and graphs produced a valid α=2/3 separator or stayed under the √8m bound. Since the paper's second application is the claim that balanced woods provide an efficient tool for computing separators, the authors should report per-graph success rates and the distribution of boundary sizes (for instance, a table of medians and IQRs over seeds), and state explicitly whether every tested instance satisfied the stated bound.

minor comments (5)

[Abstract and Section 2] The abstract says "planar graphs," but the paper actually studies planar triangulations; the terminology should be aligned throughout.
[Section 2.1] The notion "well balanced if a majority of vertices have a small defect" is not formalized; the authors should specify a threshold (e.g., δ(v) ≤ 1) or state the exact cutoff used in the plots.
[Section 2.3, Fig. 2] The runtime comparison against previous C implementations is not apples-to-apples: the present Java implementation runs on an i7-5600U with 1GB RAM, while the cited C implementations run on a Xeon X5650 with 48.4GB RAM. The authors should either run a controlled comparison on the same machine or explicitly label the comparison as indicative only.
[Appendix A.2] The queue list is written as "Q0, Q2, ..., Qk−1," which appears to omit Q1; it should be "Q0, Q1, ..., Qk−1." In addition, the text mentions processing "more than 3 M vertices per second" for random triangulations, while Section 2.3 reports 1.43M–1.92M vertices per second; these numbers should be reconciled.
[Fig. 3] In the right chart, the axis labeled "boundary size" should state whether the value is normalized by √m, √n, or an absolute count; the caption lists √n, √m, √8n, and √8m without making the normalization explicit.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the experimental results are not forced by construction, and the paper's self-citations are not load-bearing.

full rationale

The paper makes no first-principles derivation; its claims are explicitly empirical and are accompanied by the caveat that no theoretical guarantees are provided. The heuristic's objective (increasing balance by retarding vertices with few incoming edges during shelling, with a fixed queue count k=5) is distinct from the evaluation metrics (edge-length evenness el, separator boundary size, and separator balance), which are computed only after the Schnyder wood is produced. No parameter is fitted to the target quantities: the separator procedure scans all vertices and selects the one minimizing cycle length subject to the balance ratio, rather than fitting a parameter to observed separator sizes. The Fig. 3 correlation between average defect and quality is a potential validity concern because reversing oriented triangles changes more than the balance metric, but that is a causal-interpretation issue, not circularity: balance is neither defined in terms of layout quality nor used to compute it. The author's self-citations ([8], [9]) appear only as background references for compact data structures and higher-genus generalizations, and they do not justify the paper's central experimental claims. Thus no circular step can be exhibited from the paper's own equations or definitions.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard Schnyder wood theory and shelling correctness plus three domain assumptions about the heuristic's validity, dataset representativeness, and quality metrics. The only hand-set numeric parameter in the main algorithm is the queue count k=5. No new physical or formal entities are introduced.

free parameters (1)

k, number of priority queues = 5
Hand-set constant in the truncated shelling heuristic (Appendix A.2); controls the trade-off between balance quality and runtime. The paper does not report sensitivity to k.

assumptions (4)

standard math Every planar triangulation admits a Schnyder wood, and vertex shelling computes one.
Foundational result used in Section 2.1 and Appendix A.1, attributed to Schnyder [27] and Brehm [7].
domain assumption The retarded conquest priority rule still yields a valid Schnyder wood.
The paper argues termination and correctness informally in Appendix A.2 but gives no formal proof that the priority rule preserves the Schnyder invariants in all cases.
domain assumption The tested graph collection is representative of the planar triangulations for which the practical claim is intended.
Datasets from aim@shape, Thingi10k, random and Delaunay triangulations, and synthetic grids (Section 2.3); if unrepresentative, the empirical conclusions do not generalize.
domain assumption The edge-length metric el and the balance ratio alpha=2/3 are valid quality criteria for drawings and separators.
The paper adopts el from [14] and alpha=2/3 from the separator literature (Section 2.3) without independent justification.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Balanced Schnyder woods for planar triangulations: an experimental study with applications to graph drawing and graph separators." pith.science (2026). https://pith.science/paper/ZNXAXNY4

@misc{pith2026190806688,
  author       = {Pith},
  title        = {Pith review of: Balanced Schnyder woods for planar triangulations: an experimental study with applications to graph drawing and graph separators},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZNXAXNY4}},
  note         = {Machine review of arXiv:1908.06688}
}

read the original abstract

In this work we consider balanced Schnyder woods for planar graphs, which are Schnyder woods where the number of incoming edges of each color at each vertex is balanced as much as possible. We provide a simple linear-time heuristic leading to obtain well balanced Schnyder woods in practice. As test applications we consider two important algorithmic problems: the computation of Schnyder drawings and of small cycle separators. While not being able to provide theoretical guarantees, our experimental results (on a wide collection of planar graphs) suggest that the use of balanced Schnyder woods leads to an improvement of the quality of the layout of Schnyder drawings, and provides an efficient tool for computing short and balanced cycle separators.

Figures

Figures reproduced from arXiv: 1908.06688 by the authors.

**Figure 1.** (a) A planar triangulation endowed with a Schnyder wood. (b) a separator (A, B, S) obtained from the Schnyder wood. (c) three Schnyder woods of the same portion of a spherical grid: our heuristic leads to a majority of balanced vertices (white circles), while the minimal Schnyder wood is strongly unbalanced. (Right chart) Evaluation of the balance of Schnyder woods (tests are repeated with 500 random seeds). the wo… view at source ↗

**Figure 2.** Evaluation of timing costs over 100 executions (allocating 1GB of RAM for the JVM): timings are expressed as a function of the size (millions of vertices). follows: for each vertex v check whether the two sets A = Int(Ri(v) ∪ Ri+1(v)) and B = Int(Ri+2(v)) satisfy the prescribed balance ratio for at least one index i ∈ {0, 1, 2} (indices are modulo 3, and Int(R) denotes the set of inner vertices of a region R): then … view at source ↗

**Figure 3.** For a fixed initial seed, we generate a sequence of Schnyder woods by starting from a well balanced Schnyder wood (computed with our heuristic) and by randomly reversing ccw oriented triangles. In the charts we plot the layout and separator quality as functions of the average defect δavg of the corresponding Schnyder wood. that our heuristic leads to well balanced Schnyder woods. Our heuristic performs particularly … view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: We evaluate the quality of our simple cycle separators obtained from our balanced Schnyder woods (tests are repeated using 200 random seeds). The left charts report the boundary sizes, while the right charts show the plots of the separator balance (the normalized size …

**Figure 5.** Figure 5: The pictures above illustrate some steps of our heuristic for computing a balanced Schnyder wood of a planar triangulation. Yellow circles represent boundary vertices incident to chordal edges (they are not free and cannot be removed). vertex, we perform a colorOrien…

**Figure 6.** Figure 6: Post-processing phase: these charts show the effect of the post-processing phase that consists in reversing oriented triangles in order to increase the number of balanced vertices. For a given fixed choice of the initial seed we evaluate the number of balanced vertices…

**Figure 7.** Figure 7: Effect of the post-processing phase on the quality of the Schnyder layout and on the size of the separators. All results are obtained for a fixed choice o the initial seed. the faces and reversing oriented triangles can be even 5.5 slower than computing a balanced Schn…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 22 canonical work pages

[1]

Journal of Combinatorial Theory, Series A 116(1), 55–75 (2009), https://hal

Bernardi, O., Bonichon, N.: Catalan’s intervals and realizers of triangulations. Journal of Combinatorial Theory, Series A 116(1), 55–75 (2009), https://hal. archives-ouvertes.fr/hal-00143870, 22 pages

work page 2009
[2]

Discrete Mathematics 298, 104–114 (2005), https: //hal.archives-ouvertes.fr/hal-00307593

Bonichon, N.: A Bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths. Discrete Mathematics 298, 104–114 (2005), https: //hal.archives-ouvertes.fr/hal-00307593

work page 2005
[3]

Algorithmica 47(4), 399–420 (2007), https://doi.org/10.1007/ s00453-006-0177-6

Bonichon, N., Felsner, S., Mosbah, M.: Convex drawings of 3-connected plane graphs. Algorithmica 47(4), 399–420 (2007), https://doi.org/10.1007/ s00453-006-0177-6

work page 2007
[4]

In: Graph Theoretic Con- cepts in Computer Science - 36th International Workshop, WG 2010

Bonichon, N., Gavoille, C., Hanusse, N., Ilcinkas, D.: Connections between theta- graphs, delaunay triangulations, and orthogonal surfaces. In: Graph Theoretic Con- cepts in Computer Science - 36th International Workshop, WG 2010. pp. 266–278 (2010), https://doi.org/10.1007/978-3-642-16926-7_25

work page doi:10.1007/978-3-642-16926-7_25 2010
[5]

In: Automata, Languages and Programming, 37th Interna- tional Colloquium, ICALP 2010

Bonichon, N., Gavoille, C., Hanusse, N., Perkovic, L.: Plane spanners of max- imum degree six. In: Automata, Languages and Programming, 37th Interna- tional Colloquium, ICALP 2010. pp. 19–30 (2010), https://doi.org/10.1007/ 978-3-642-14165-2_3

work page 2010
[6]

Borradaile, G., Iglesias, J., Migler, T., Ochoa, A., Wilfong, G.T., Zhang, L.: Egal- itarian graph orientations. J. Graph Algorithms Appl. 21(4), 687–708 (2017), https://doi.org/10.7155/jgaa.00435

work page doi:10.7155/jgaa.00435 2017
[7]

Master’s Thesis, FB Mathematik und Informatik, Freie Universit¨ at Berlin (2000)

Brehm, E.: 3-orientations and Schnyder 3-tree-decompositions. Master’s Thesis, FB Mathematik und Informatik, Freie Universit¨ at Berlin (2000)

work page 2000
[8]

JoCG 9(1), 247–289 (2018), https://doi.org/10.20382/jocg.v9i1a8

Castelli Aleardi, L., Devillers, O.: Array-based compact data structures for tri- angulations: Practical solutions with theoretical guarantees. JoCG 9(1), 247–289 (2018), https://doi.org/10.20382/jocg.v9i1a8

work page doi:10.20382/jocg.v9i1a8 2018

Show all 28 references

[9]

Discrete & Computational Geometry 42(3), 489–516 (2009), https://hal.inria.fr/hal-00712046v1

Castelli Aleardi, L., Fusy, ´E., Lewiner, T.: Schnyder woods for higher genus triangu- lated surfaces, with applications to encoding. Discrete & Computational Geometry 42(3), 489–516 (2009), https://hal.inria.fr/hal-00712046v1

2009
[10]

Discrete & Computational Geometry 57(3), 507–544 (2017), https://doi.org/10.1007/ s00454-016-9832-0

Despr´ e, V., Gon¸ calves, D., L´ evˆ eque, B.: Encoding toroidal triangulations. Discrete & Computational Geometry 57(3), 507–544 (2017), https://doi.org/10.1007/ s00454-016-9832-0

2017
[11]

Discrete & Computational Geometry 43(2), 375–392 (2010), https://doi.org/10.1007/s00454-009-9235-6

Dhandapani, R.: Greedy drawings of triangulations. Discrete & Computational Geometry 43(2), 375–392 (2010), https://doi.org/10.1007/s00454-009-9235-6

2010 doi
[12]

Felsner, S.: Lattice structures from planar graphs. Electr. J. Comb. 11(1) (2004), http://www.combinatorics.org/Volume_11/Abstracts/v11i1r15.html

2004
[13]

Felsner, S., Zickfeld, F.: On the number of planar orientations with prescribed degrees. Electr. J. Comb. 15(1) (2008)

2008
[14]

In: Graph Drawing - 20th International Symposium

Fowler, J.J., Kobourov, S.G.: Planar preprocessing for spring embedders. In: Graph Drawing - 20th International Symposium. pp. 388–399 (2012)

2012
[15]

ACM Journal of Experimental Algorithmics 21(1), 2.2:1–2.2:24 (2016)

Fox-Epstein, E., Mozes, S., Phothilimthana, P.M., Sommer, C.: Short and simple cycle separators in planar graphs. ACM Journal of Experimental Algorithmics 21(1), 2.2:1–2.2:24 (2016)

2016
[16]

Combinatorica 10(1), 41–51 (1990)

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)

1990
[17]

Discrete & Computational Geometry 51(1), 67– 131 (2014), http://dx.doi.org/10.1007/s00454-013-9552-7 8 L

Gon¸ calves, D., L´ evˆ eque, B.: Toroidal maps: Schnyder woods, orthogonal surfaces and straight-line representations. Discrete & Computational Geometry 51(1), 67– 131 (2014), http://dx.doi.org/10.1007/s00454-013-9552-7 8 L. Castelli Aleardi

2014 doi
[18]

Com- put

Gotsman, C.: On the optimality of valence-based connectivity coding. Com- put. Graph. Forum 22(1), 99–102 (2003), https://doi.org/10.1111/1467-8659. t01-1-00649

2003 doi
[19]

ACM Journal of Experimental Algorithmics 14 (2009), https://doi.org/10.1145/1498698.1571635

Holzer, M., Schulz, F., Wagner, D., Prasinos, G., Zaroliagis, C.D.: Engineering pla- nar separator algorithms. ACM Journal of Experimental Algorithmics 14 (2009), https://doi.org/10.1145/1498698.1571635

2009
[20]

In: Encyclopedia of Algorithms, pp

Kobourov, S.G.: Canonical orders and schnyder realizers. In: Encyclopedia of Algorithms, pp. 277–283. Springer (2016), http://dblp.uni-trier.de/rec/bib/ reference/algo/Kobourov16

2016
[21]

Li, Y., Sun, X., Watson, S.S.: Schnyder woods, sle(16), and liouville quantum gravity. Tech. Rep. arXiv:1705.03573v1 [math.PR], ArXiV (May 2016), https: //arxiv.org/abs/1705.03573

2016 arXiv
[22]

Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Applied Math. 36(2), 177–189 (1979)

1979
[23]

Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615–627 (1980), https://doi.org/10.1137/0209046

1980 doi
[24]

Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. J. Comput. Syst. Sci. 32(3), 265–279 (1986), https://doi.org/10.1016/ 0022-0000(86)90030-9

1986
[25]

PIGALE, Public Implementation of a Graph Algorithm Library and Editor, http://pigale.sourceforge.net/
[26]

Al- gorithmica 46(3-4), 505–527 (2006)

Poulalhon, D., Schaeﬀer, G.: Optimal coding and sampling of triangulations. Al- gorithmica 46(3-4), 505–527 (2006)

2006
[27]

In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Schnyder, W.: Embedding planar graphs on the grid. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. vol. 90, pp. 138–148 (1990),http: //departamento.us.es/dma1euita/PAIX/Referencias/schnyder.pdf

1990
[28]

In: Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

Spielman, D.A., Teng, S.: Disk packings and planar separators. In: Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996. pp. 349–358 (1996), https://doi.org/10.1145/237218.237404 A Appendix: computation of balanced Schnyder woods A.1 Incremental vertex c...

1996

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Journal of Combinatorial Theory, Series A 116(1), 55–75 (2009), https://hal

Bernardi, O., Bonichon, N.: Catalan’s intervals and realizers of triangulations. Journal of Combinatorial Theory, Series A 116(1), 55–75 (2009), https://hal. archives-ouvertes.fr/hal-00143870, 22 pages

work page 2009

[2] [2]

Discrete Mathematics 298, 104–114 (2005), https: //hal.archives-ouvertes.fr/hal-00307593

Bonichon, N.: A Bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths. Discrete Mathematics 298, 104–114 (2005), https: //hal.archives-ouvertes.fr/hal-00307593

work page 2005

[3] [3]

Algorithmica 47(4), 399–420 (2007), https://doi.org/10.1007/ s00453-006-0177-6

Bonichon, N., Felsner, S., Mosbah, M.: Convex drawings of 3-connected plane graphs. Algorithmica 47(4), 399–420 (2007), https://doi.org/10.1007/ s00453-006-0177-6

work page 2007

[4] [4]

In: Graph Theoretic Con- cepts in Computer Science - 36th International Workshop, WG 2010

Bonichon, N., Gavoille, C., Hanusse, N., Ilcinkas, D.: Connections between theta- graphs, delaunay triangulations, and orthogonal surfaces. In: Graph Theoretic Con- cepts in Computer Science - 36th International Workshop, WG 2010. pp. 266–278 (2010), https://doi.org/10.1007/978-3-642-16926-7_25

work page doi:10.1007/978-3-642-16926-7_25 2010

[5] [5]

In: Automata, Languages and Programming, 37th Interna- tional Colloquium, ICALP 2010

Bonichon, N., Gavoille, C., Hanusse, N., Perkovic, L.: Plane spanners of max- imum degree six. In: Automata, Languages and Programming, 37th Interna- tional Colloquium, ICALP 2010. pp. 19–30 (2010), https://doi.org/10.1007/ 978-3-642-14165-2_3

work page 2010

[6] [6]

Borradaile, G., Iglesias, J., Migler, T., Ochoa, A., Wilfong, G.T., Zhang, L.: Egal- itarian graph orientations. J. Graph Algorithms Appl. 21(4), 687–708 (2017), https://doi.org/10.7155/jgaa.00435

work page doi:10.7155/jgaa.00435 2017

[7] [7]

Master’s Thesis, FB Mathematik und Informatik, Freie Universit¨ at Berlin (2000)

Brehm, E.: 3-orientations and Schnyder 3-tree-decompositions. Master’s Thesis, FB Mathematik und Informatik, Freie Universit¨ at Berlin (2000)

work page 2000

[8] [8]

JoCG 9(1), 247–289 (2018), https://doi.org/10.20382/jocg.v9i1a8

Castelli Aleardi, L., Devillers, O.: Array-based compact data structures for tri- angulations: Practical solutions with theoretical guarantees. JoCG 9(1), 247–289 (2018), https://doi.org/10.20382/jocg.v9i1a8

work page doi:10.20382/jocg.v9i1a8 2018