Pith. sign in

REVIEW 3 major objections 4 minor 47 references

Rectangular Duals on the Cylinder and the Torus

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read This paper proves that a cylindrical graph has a cylindrical rectangular dual exactly when it is properly triangulated cylindrical, and that a supplied toroidal regular edge labeling is either unrealizable, orbital, or slanted, each…

desk verdict A clean and substantial step on rectangular duals for cylinder and torus, with one load-bearing verification gap in the cylindrical characterization that needs to be filled before the paper is fully trustworthy. read the letter →

arxiv 2506.07170 v1 pith:YXPKJ7Q6 submitted 2025-06-08 cs.CG cs.DM

Therese Biedl , Philipp Kindermann , Jonathan Klawitter This is my paper
classification cs.CGcs.DM MSC 05C1005C6268R10
keywords rectangulardualcontactrepresentationregularedgelabelingtoruscylinderproperlytriangulatedgraphflatdrawing
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

Rectangular duals—contact representations by axis-aligned rectangles with no four corners meeting—are classical for plane graphs, used in floor plans and VLSI layout. This paper extends them to graphs embedded on a cylinder or a flat torus. Its central cylindrical result is a complete if-and-only-if: a graph with a fixed cylindrical embedding admits a cylindrical rectangular dual precisely when it is a properly triangulated cylindrical (PTC) graph, meaning every loop, parallel edge, and separating triangle is non-contractible, plus degree conditions at vertices paired with loop-incident neighbors, and the proof gives a linear-time construction. For the torus, the paper assumes a regular edge labeling is supplied and proves a trichotomy: the labeling is unrealizable, orbital (every monochromatic cycle lies parallel to an orbit), or slanted (realizable but not orbital), with linear-time recognition and linear- or quadratic-time construction of the corresponding rectangular dual. The value for a curious reader is that graph layout tools that previously worked only on the plane now have exact tests and constructions for two topologically nontrivial surfaces.

What carries the argument

The engine is the regular edge labeling (REL): a two-coloring and orientation of edges recording whether two rectangles touch by horizontal or vertical sides, satisfying at each vertex the cyclic pattern blue-in, red-in, blue-out, red-out. The paper defines properly triangulated cylindrical and toroidal graphs (PTC and PTT) as the exact conditions under which such labelings can exist, translating non-contractibility of loops, parallel edges, and separating triangles into combinatorial constraints. For the torus the deciding tool is a pair of left-first and right-first directed cycles in each color class; Proposition 4 equates an orbital REL with both cycles being orbit-advancing and orbit-enclosing relative to the meridian and horizon. Once the REL is orbital, a feedback closed walk—a weakly simple non-contractible walk crossing every cycle of the dual—is found and used to split the color graph into a cylindrical graph whose dual is acyclic, so that rectangle coordinates come from longest paths in the same way as in the planar algorithm. Slanted RELs are handled by cutting the covering plane into patches and assembling the patch duals into a parallelogram bounded by curves parallel to the meridian and horizon.

What would settle it

Enumerate all small internally triangulated cylindrical graphs and check whether any graph satisfying the PTC conditions nevertheless has no cylindrical rectangular dual; the most likely place to look is the two-leg case of Lemma 4, where the proof relies on an unverified adaptation of the planar removable-set construction.

Watch

Extended reading notes

Core claim

On the cylinder, the central claim is that a fixed cylindrical embedding has a rectangular dual on a rectangular flat cylinder if and only if the graph is PTC. The proof constructs the dual in linear time by first building a cylindrical regular edge labeling whose blue graph is acyclic, then extending that labeling to an orbital toroidal REL on a properly triangulated toroidal supergraph, running the toroidal rectangular-dual algorithm, and deleting the added vertices. On the torus, the central claim is the trichotomy of Theorem 5: a supplied toroidal REL is unrealizable when some edge lies on no monochromatic cycle, orbital when every edge lies on a cycle parallel to the corresponding orbit, and slanted when it is realizable but not orbital; this is decided in linear time from left-first and right-first cycles and their algebraic crossing numbers with the meridian and horizon. An orbital REL yields a rectangular dual on a rectangular flat torus in linear time, while a slanted REL yields one on a slanted flat torus in quadratic time. The paper further establishes that realizability is exactly what a toroidal rectangular dual realizing the given REL requires.

Load-bearing premise

The whole cylindrical construction leans on an unproved verification: in the two-leg case of Lemma 4, the removable set found by the planar ordering lemma is claimed to work unchanged for cylindrical graphs with only 'as one easily verifies,' and if that check fails for some graph, the induction that builds the cylindrical edge labeling no longer goes through.

Editorial extensions

If this is right

  • As a direct corollary of the cylindrical characterization, a graph can be filtered in linear time: if the PTC conditions hold, a cylindrical rectangular dual on a rectangular flat cylinder is produced; if they fail, none exists.
  • For toroidal graphs with a supplied REL and embedding, no search or backtracking is needed: the left-first and right-first cycle test decides in linear time whether a rectangular or slanted flat torus suffices or whether no dual realizes the given REL.
  • Because non-contractible separating triangles, parallel edges, and loops are permitted, cylindrical and toroidal rectangular duals exist for a strictly larger class of graphs than planar rectangular duals.
  • The proofs are constructive: linear time for cylindrical and orbital-toroidal inputs, quadratic time for slanted-toroidal inputs, with the rectangular dual itself output, not merely a yes-or-no answer.
  • The slanted-versus-orbital distinction gives a precise sense in which allowing the flat torus to be slanted is a genuine extra degree of freedom, and the paper's example shows some graphs need it.

Reading between the lines

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

  • The cylinder proof suggests a template the paper does not pursue: the same minimal obstruction set of non-contractible separating triangles, loops, and parallel edges might characterize rectangular duals on other non-planar surfaces such as the projective plane or the Klein bottle.
  • The paper leaves open whether every properly triangulated toroidal graph has a realizable REL; because realizability is decidable in linear time, a computational search over small toroidal triangulations with their balanced 4-orientations could quickly test this conjecture.
  • For applications that require grid-aligned periodic layouts, the orbital/slanted distinction implies a concrete design choice: either accept slanted fundamental polygons or restrict the input class, and one could quantify the area blow-up when forcing a slanted dual onto a rectangular flat torus.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper generalizes planar rectangular duals to two surfaces. For cylindrical graphs it defines properly triangulated cylindrical (PTC) graphs and claims, via Lemma 6 and Theorem 8, that a cylindrical graph admits a cylindrical rectangular dual if and only if it is PTC. For toroidal graphs, it assumes a supplied regular edge labeling (REL) and a fixed embedding on a flat torus, then gives a linear-time trichotomy (Theorem 5) into unrealizable, orbital, and slanted RELs. It constructs rectangular duals on the rectangular flat torus for orbital RELs (Theorem 6) and on a slanted flat torus for slanted RELs (Theorem 7), with quadratic running time in the latter case. The cylindrical result is obtained by first constructing a cylindrical REL (Lemma 5, based on Lemma 4) and then reducing to the toroidal construction of Theorem 6.

Significance. If the proof gaps are closed, this is a substantial contribution: it provides the first complete characterization of cylindrical rectangular duals and the first systematic treatment of toroidal rectangular duals, including the subtle distinction between orbital and slanted flat tori. The main strengths are the crisp PTC characterization, the linear-time recognition of REL types via left-first/right-first cycles, and the explicit constructive algorithms that adapt He's planar algorithm to surfaces. The paper is also honest about the open problem of toroidal graphs without a given REL. However, two load-bearing proof steps are currently asserted rather than fully demonstrated, so the results cannot yet be considered fully established.

major comments (3)
  1. [Section 4.1, Lemma 4, Case 3] The transfer of Biedl and Derka [6, Lemma 1] to the PTC setting is asserted with 'one easily verifies' and a footnote claiming the proof 'goes through verbatim' as long as all separating triangles contain the pre-specified edge. This is load-bearing because Lemma 5's induction and therefore Theorem 8's sufficiency direction require that G\V' is again PTC. The verification is not a formality: H+ may have separating triangles containing {ci,cj}, while G itself may have loops, parallel edges, and non-contractible separating triangles. To conclude that G\V' is PTC one must check at least that the new outer face f'_t has no chord and no non-consecutive repeated vertex (where f'_t may traverse vertices on the other arc of f_t and possibly the 2-leg center x), that all loops, parallel edges, and separating triangles of G\V' remain non-contractible, and that the degree condition holds at every vertex incident to a parallel edge whose neighbor has a loop after the deletion changes which vertices lie on f'_t. None of these checks appear in the manuscript. Please provide a full proof of the transfer or state the additional hypotheses on G under which the Biedl--Derka proof indeed goes through.
  2. [Section 3.2, proof of Theorem 7] The final step of the slanted construction replaces the 'bizarrely shaped polygon' Q' by the parallelogram spanned by the four corner points p1,p2,p3,p4 and asserts that Q∩\tilde{R} is the desired toroidal rectangular dual. This step is not justified: the text does not prove that the parallelogram is a fundamental parallelogram of the same flat torus, that it contains exactly one copy of each vertex-rectangle, that its boundary curves are parallel to M and H, or that the no-four-rectangles-share-a-point condition and the full-coverage condition are preserved under this replacement. The runtime analysis also relies on unstated structural bounds, e.g., that each side of Q intersects only O(n) tiles and that each patch is translated only O(n) times in a way compatible with the final O(n|V(G)|) bound. A rigorous proof of the parallelogram step is essential because the entire slanted-torus existence claim rests on it.
  3. [Section 4.2, Theorem 8] The reduction from cylindrical to toroidal RELs is compressed into two 'one verifies' claims: that the extended graph \hat{G} is PTT and that the assigned colors and directions complete L to a toroidal REL \hat{L}. More importantly, the argument that \hat{L} is 1-orbital for a suitable choice of meridian M uses Lemma 1 to produce a blue cycle and then declares that cycle to be M, but it is not shown that this choice is compatible with the original embedding of G on the cylinder, nor that after deleting R(v_t) and R(v_s) the resulting flat-cylinder representation has the two outer faces bounded by horizontal segments as required by the definition of a cylindrical rectangular dual. Please expand this verification or state precisely which properties of the reduction are being assumed.
minor comments (4)
  1. [Section 2.1, page 4] Typo: 'Eucledian' should be 'Euclidean'.
  2. [Section 2.2, PTC definition vs. Section 4 restatement] The degree-condition for PTC graphs is stated slightly differently in Section 2.2 (bulleted list) and in the restatement at the start of Section 4. In particular, the Section 4 version adds 'deg(u)=5 and at least one neighbour of u is not incident to a loop' as a separate case, which is not phrased in the Section 2.2 bullets. Please reconcile the two formulations so the condition is unambiguous.
  3. [Section 3.1, Figure 10 caption] The phrase 'not1-orbit-advancing' in the caption should read 'not 1-orbit-advancing'.
  4. [Abstract] The abstract states that for toroidal graphs 'we can test whether the graph has a toroidal rectangular dual if we are additionally given a regular edge labeling' and then states a second test about rectangular flat tori; the second test also requires a supplied REL and a fixed embedding, which is only clarified later in the introduction. Please make the premises in the abstract explicit.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper's cylindrical and toroidal characterizations are proved from external published tools and geometric arguments, not from restating their inputs.

full rationale

I walked the derivation chain and found no step in which a claimed prediction or characterization reduces by construction to its own inputs. The cylindrical characterization (PTC graphs admit cylindrical rectangular duals) is proved in two directions: Lemma 6 gives a geometric necessity argument from rectangular duals to the PTC properties, and Lemma 5 plus Theorem 8 gives sufficiency by constructing a cylindrical REL and then reducing to the toroidal construction. Neither direction fits a parameter to the data it claims to predict. The toroidal trichotomy (Theorem 5) is stated for a given REL and embedding; it is a decision procedure whose correctness is argued through Proposition 4, Observation 3, and Lemma 1, none of which presuppose the answer. The construction theorems (Theorems 6 and 7) adapt He's published REL-based algorithm and are not renaming a known empirical pattern. The only self-citation is to Biedl and Derka's (3,1)-canonical ordering, used in Lemma 4 as a prior published lemma; the paper explicitly says it cannot use that work as a black box and re-does and expands the argument. This is real external support, not a self-citation chain that forces the conclusion. The skeptical concern about the 'one easily verifies' transfer in Lemma 4, Case 3, is a potential proof gap or correctness risk, not circularity: no equation or definition in the paper is equivalent to the target result by construction, and no fitted or renamed quantity pre-encodes the answer. Hence the honest finding is no significant circularity.

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

No free parameters are fitted. The paper relies on standard facts about torus topology and on cited prior algorithms, namely He's REL-based rectangular dual construction and Biedl-Derka's (3,1)-ordering. The main new objects, such as orbital, slanted, and unrealizable RELs and feedback closed walks, are mathematical definitions rather than postulated entities.

assumptions (4)
  • standard math The fundamental group of the flat torus is generated by the meridian and horizon, and the algebraic crossing number of two curves is computed from their homotopy classes as m(C)h(C') - h(C)m(C').
    Used throughout Section 2.1 and in Lemma 1, Observations 1-3, and Proposition 4 to derive homotopy class conditions for cycles.
  • standard math Biedl and Derka's Lemma 1 provides a (3,1)-canonical-style vertex removal set for 4-connected planar triangulations, and Lemma 4 of this paper extends it to PTC graphs.
    Invoked in Section 4.1, Lemma 4 Case 3, to find V' for the cylindrical REL construction; the extension is asserted but not fully proved in the text.
  • domain assumption The input toroidal graph comes with a fixed embedding on the flat torus and, for the torus results, a given regular edge labeling L that satisfies the REL property.
    Theorems 5-7 take L and the embedding as input; the paper states in Section 5 that deciding existence of a realizable REL without one is open.
  • domain assumption A rectangular dual is defined with axis-aligned rectangles and the no-four-rectangles-share-a-point condition, and on the cylinder or torus the union fills a strip or the entire flat torus.
    These definitions in Section 2.2 shape the PTC and PTT necessary conditions and the construction algorithms.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Rectangular Duals on the Cylinder and the Torus." pith.science (2026). https://pith.science/paper/YXPKJ7Q6

@misc{pith2026250607170,
  author       = {Pith},
  title        = {Pith review of: Rectangular Duals on the Cylinder and the Torus},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YXPKJ7Q6}},
  note         = {Machine review of arXiv:2506.07170}
}
abstract

A rectangular dual of a plane graph $G$ is a contact representation of $G$ by interior-disjoint rectangles such that (i) no four rectangles share a point, and (ii) the union of all rectangles is a rectangle. In this paper, we study rectangular duals of graphs that are embedded in surfaces other than the plane. In particular, we fully characterize when a graph embedded on a cylinder admits a cylindrical rectangular dual. For graphs embedded on the flat torus, we can test whether the graph has a toroidal rectangular dual if we are additionally given a \textit{regular edge labeling}, i.e. a combinatorial description of rectangle adjacencies. Furthermore we can test whether there exists a toroidal rectangular dual that respects the embedding and that resides on a flat torus for which the sides are axis-aligned. Testing and constructing the rectangular dual, if applicable, can be done efficiently.

Figures

Figures reproduced from arXiv: 2506.07170 by the authors.

Figure 1
Figure 1. A rectangular dual on the cylinder and on the torus. [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Rectangular duals on different surfaces. [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. While this graph does not admit a rectangular dual on a rectangular flat torus, with the [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figures from the paper (20 more)
Figure 4
Figure 4. Figure 4: Extract of the UCP shows two curves Cℓ, Cr in homotopy class (−1, 3) and (2, 1) cross 7 = (−1) · 1 − 3 · 2 times. Orbits and Homotopy Classes. The sides of T are two non-contractible curves M and H that intersect exactly once. The vertical curve M is called meridian or…
Figure 5
Figure 5. Figure 5: For cylindrical graphs, we can assume that the fundamental polygon [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]
Figure 6
Figure 6. Figure 6: Obtaining a weakly-simple closed walk C from two cycles Cℓ and Cr. Lemma 1 Let G be a directed essentially-acyclic toroidal graph on T. Let Cℓ and Cr be two cycles where Cℓ crosses Cr only right-to-left and at least once, and Cℓ and Cr may only touch unidirectionally. …
Figure 7
Figure 7. Figure 7: For the same two curves as in [PITH_FULL_IMAGE:figures/full_fig_p010_7.png]
Figure 8
Figure 8. Figure 8: For the proof of Lemma 1, we show that the cycle C cannot touch itself. of cycle-pieces, therefore C includes this entire side of the patch, Cℓ[s, x] ∪ Cr[x, t] ⊂ C. But this directed path has repeated points (at a, b, c, d), so it contains a directed cycle. Furthermor…
Figure 9
Figure 9. Figure 9: No realizable REL has reverse-parallel cycles. [PITH_FULL_IMAGE:figures/full_fig_p012_9.png]
Figure 10
Figure 10. Figure 10: This toroidal REL is 1-orbital but not 2-orbital. One can verify that every blue edge is 1-orbital (use vertical paths for vertical edges, and combine vertical paths with exactly one edge each of Cℓ and Cr for edges within Cℓ/Cr). But the left-first cycle Cℓ of L1(G) …
Figure 11
Figure 11. Figure 11: Given an orbital REL, we split L1(G) and L2(G) along orbital feedback cycles and then use He’s algorithm to obtain a rectangular dual R on the flat rectangular torus. about D. First, ˆı(D, C′ ) ≥ 0 for any cycle C ′ in Li(G) since dual edges are directed to cross only…
Figure 12
Figure 12. Figure 12: The feedback cycle C1 (obtained from Cℓ and Cr) of this slanted REL {L1,L2} is weakly simple. Hence, L1(G) ∥ C1 contains four copies of the vertices on the path C1[u, v] shared by Cℓ and Cr. cycle Ci of Li(G) with Lemma 3, the cylindrical graph Li(G) ∥ Ci , and let L …
Figure 13
Figure 13. Figure 13: Constructing a feedback closed walk C for L1(G) in the proof of Lemma 3. of G on T. □ For a slanted REL, computing rectangle-coordinates is significantly more complicated since the consistent numberings d1 and d2 do not directly translate to coordinates in the slanted…
Figure 14
Figure 14. Figure 14: Feedback circuits Ci for i ∈ [2]. P4 a b c d f g h i e a b c d f g h i e a b c d f g h i e a b c d f g h i e a b c d f g h i e a b c d f g h i e a b c d f g h i e a b c d f g h i e a b c d f g h i e a b c d f g h i e a b c d f g h i e a b c d f g h i e [PITH_FULL_IMA…
Figure 16
Figure 16. Figure 16: Compute the consistent numberings di(·) in L ⋆ i (G)∥Ci for i ∈ [2] [PITH_FULL_IMAGE:figures/full_fig_p022_16.png]
Figure 17
Figure 17. Figure 17: Rectangular duals of the five patches. a i f g f g e f h a i f g f g e f h i c a h g a f h i b d h i a a i b d i g c a e i c a h g a f h i b d h i a a i f g f g e f h a i b d i g c a e a f h i b d i c a h i g c a h g h i a a i b d i g c a e i c a h g h i a a i f g f g…
Figure 18
Figure 18. Figure 18: Putting the rectangular duals of the patches together in the tiling of the plane and [PITH_FULL_IMAGE:figures/full_fig_p023_18.png]
Figure 19
Figure 19. Figure 19: The final rectangular dual [PITH_FULL_IMAGE:figures/full_fig_p024_19.png]
Figure 20
Figure 20. Figure 20: For Lemma 4, first two cases of finding vertex set V ′ and obtaining a cylindrical REL. Case 2 – enclosing parallel pair: We first consider the special case that ft is bounded by a pair of parallel edges incident to c1 and c2 whose two neighbors x and y span a pair of…
Figure 21
Figure 21. Figure 21: For Lemma 4, next two cases of finding vertex set V ′ and obtaining a cylindrical REL. One easily verifies that the same set V ′ works for our lemma. 2 Case 4 – there is no 2-leg: We distinguish four subcases to pick z. (i) If ft is a loop, let z be the sole vertex on…
Figure 22
Figure 22. Figure 22: Processing first a singleton {z} and then a fan {z1, z2} to construct a cylindrical REL. choice of z. If y is not on ft and x = y, then {x, y} is a loop (because G is triangulated) and not a chord (and Case 1 applies). The remaining properties are easily checked as be…
Figure 23
Figure 23. Figure 23: Some non-simple cylindrical graphs cannot be realized by cylindrical rectangular duals [PITH_FULL_IMAGE:figures/full_fig_p029_23.png]
Figure 24
Figure 24. Figure 24: To construct a rectangular dual of a PTC graph with a cylindrical REL, we extend it [PITH_FULL_IMAGE:figures/full_fig_p030_24.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

47 extracted references · 37 canonical work pages

  1. [1]

    Kobourov, Sergey Pupyrev, André Schulz, and Torsten Ueckerdt

    Jawaherul Alam, David Eppstein, Michael Kaufmann, Stephen G. Kobourov, Sergey Pupyrev, André Schulz, and Torsten Ueckerdt. Contact graphs of circular arcs. In Frank Dehne, Jörg-Rüdiger Sack, and Ulrike Stege, editors,WADS’15, volume 9214 ofLNCS, pages 1–13. Springer, 2015.doi:10.1007/978-3-319-21840-3_1

    work page doi:10.1007/978-3-319-21840-3_1 2015

  2. [2]

    Beyondlevelplanarity: Cyclic, torus, andsimultaneouslevelplanarity

    Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrig- nani, andIgnazRutter. Beyondlevelplanarity: Cyclic, torus, andsimultaneouslevelplanarity. Theoretical Computer Science, 804:161–170, 2020.doi:10.1016/j.tcs.2019.11.024

    work page doi:10.1016/j.tcs.2019.11.024 2020

  3. [3]

    Grand-schnyder woods.Annals of Combina- torics, 2024.doi:10.1007/s00026-024-00729-8

    Olivier Bernardi, Éric Fusy, and Shizhe Liang. Grand-schnyder woods.Annals of Combina- torics, 2024.doi:10.1007/s00026-024-00729-8

    work page doi:10.1007/s00026-024-00729-8 2024

  4. [4]

    A linear time algorithm to check for the existence of a rectangular dual of a planar triangulated graph.Networks, 17(3):307–317, 1987.doi: 10.1002/net.3230170306

    Jayaram Bhasker and Sartaj Sahni. A linear time algorithm to check for the existence of a rectangular dual of a planar triangulated graph.Networks, 17(3):307–317, 1987.doi: 10.1002/net.3230170306

    work page doi:10.1002/net.3230170306 1987

  5. [5]

    Visibility representations of toroidal and Klein-bottle graphs

    Therese Biedl. Visibility representations of toroidal and Klein-bottle graphs. In Patrizio Angelini and Reinhard von Hanxleden, editors,Graph Drawing and Network Visualization (GD), volume 13764, pages 404–417. Springer, 2022.doi:10.1007/978-3-031-22203-0_29

    work page doi:10.1007/978-3-031-22203-0_29 2022

  6. [6]

    The (3,1)-ordering for 4-connected planar triangulations

    Therese Biedl and Martin Derka. The (3,1)-ordering for 4-connected planar triangulations. Journal of Graph Algorithms and Applications, 20(2):347–362, 2016.doi:10.7155/jgaa. 00396

    doi:10.7155/jgaa 2016

  7. [7]

    A bijection for essentially 4-connected toroidal triangulations.Electronic Journal of Combinatorics, 26(1):1, 2019.doi:10.37236/7897

    Nicolas Bonichon and Benjamin Lévêque. A bijection for essentially 4-connected toroidal triangulations.Electronic Journal of Combinatorics, 26(1):1, 2019.doi:10.37236/7897

    work page doi:10.37236/7897 2019

  8. [8]

    Buchsbaum, Emden R

    Adam L. Buchsbaum, Emden R. Gansner, Cecilia Magdalena Procopiuc, and Suresh Venkata- subramanian. Rectangular layouts and contact graphs.ACM Transactions on Algorithms, 4(1):8:1–8:28, 2008.doi:10.1145/1328911.1328919. 32 T. Biedl, P. Kindermann, and J. KlawitterRectangular Duals on the Cylinder and the Torus

    work page arXiv 2008

Show all 47 references
  1. [9]

    Canonical ordering for triangulations on the cylinder, with applications to periodic straight-line drawings

    Luca Castelli Aleardi, Olivier Devillers, and Éric Fusy. Canonical ordering for triangulations on the cylinder, with applications to periodic straight-line drawings. In Walter Didimo and Maurizio Patrignani, editors,Graph Drawing (GD’12), volume 7704 ofLNCS, pages 376–387. Spr...

    2013 doi

  2. [10]

    Drawinggraphs in the plane with a prescribed outer face and polynomial area

    ErinWChambers, DavidEppstein, MichaelTGoodrich, andMaartenLöffler. Drawinggraphs in the plane with a prescribed outer face and polynomial area. InGraph Drawing (GD’10), volume 6502 ofLNCS, pages 129–140. Springer, 2011.doi:10.1007/978-3-642-18469-7_12

    2011 doi

  3. [11]

    How to morph graphs on thetorus

    Erin Wolf Chambers, Jeff Erickson, Patrick Lin, and Salman Parsa. How to morph graphs on thetorus. InDánielMarx, editor,ACM-SIAM Symposium on Discrete Algorithms (SODA’21), pages 2759–2778. SIAM, 2021.doi:10.1137/1.9781611976465.164

    2021 doi

  4. [12]

    Detecting weakly simple polygons

    Hsien-Chih Chang, Jeff Erickson, and Chao Xu. Detecting weakly simple polygons. In Piotr Indyk, editor,ACM-SIAM Symposium on Discrete Algorithms (SODA’15), pages 1655–1670. SIAM, 2015.doi:10.1137/1.9781611973730.110

    2015 doi

  5. [13]

    Simple algorithms for partial and simultaneous rectangular duals with given contact orientations.Theoretical Computer Science, 919:66–74, 2022.doi:10.1016/j.tcs

    Steven Chaplick, Stefan Felsner, Philipp Kindermann, Jonathan Klawitter, Ignaz Rutter, and Alexander Wolff. Simple algorithms for partial and simultaneous rectangular duals with given contact orientations.Theoretical Computer Science, 919:66–74, 2022.doi:10.1016/j.tcs. 2022.03.031

    2022 doi

  6. [14]

    Morphing rectangular duals

    Steven Chaplick, Philipp Kindermann, Jonathan Klawitter, Ignaz Rutter, and Alexander Wolff. Morphing rectangular duals. In Patrizio Angelini and Reinhard von Hanxleden, editors, Graph Drawing and Network Visualization (GD’22), volume 13764 ofLNCS, pages 389–403. Springer, 2022...

    2022 doi

  7. [15]

    DoughNets: visualising networks using torus wrapping

    Kun-Ting Chen, Tim Dwyer, Kim Marriott, and Benjamin Bach. DoughNets: visualising networks using torus wrapping. In Regina Bernhaupt, Florian ‘Floyd’ Mueller, David Verweij, Josh Andres, Joanna McGrenere, Andy Cockburn, Ignacio Avellino, Alix Goguey, Pernille Bjøn, Shengdong Z...

    2020

  8. [16]

    Devanny, David Eppstein, and Timothy Johnson

    Giordano Da Lozzo, William E. Devanny, David Eppstein, and Timothy Johnson. Square- contact representations of partial 2-trees and triconnected simply-nested graphs. In Yoshio Okamoto and Takeshi Tokuyama, editors,International Symposium on Algorithms and Com- putation (ISAAC’...

    2017 doi

  9. [17]

    On triangle con- tact graphs.Combinatorics, Probability and Computing, 3(2):233–246, 1994.doi:10.1017/ S0963548300001139

    Hubert de Fraysseix, Patrice Ossona de Mendez, and Pierre Rosenstiehl. On triangle con- tact graphs.Combinatorics, Probability and Computing, 3(2):233–246, 1994.doi:10.1017/ S0963548300001139

    1994

  10. [18]

    A. Dean. A layout algorithm for bar-visibility graphs on the Möbius band. In Joe Marks, editor,Graph Drawing (GD’00), volume 1984 ofLNCS, pages 350–359. Springer, 2000.doi: 10.1007/3-540-44541-2_33

    1984 doi

  11. [19]

    Duncan, Michael T

    Christian A. Duncan, Michael T. Goodrich, and Stephen G. Kobourov. Planar drawings of higher-genus graphs.Journal of Graph Algorithms and Applications, 15(1):7–32, 2011. doi:10.7155/jgaa.00215. 33

    2011 doi

  12. [20]

    Triangle-free penny graphs: Degeneracy, choosability, and edge count

    David Eppstein. Triangle-free penny graphs: Degeneracy, choosability, and edge count. In Fabrizio Frati and Kwan-Liu Ma, editors,Graph Drawing and Network Visualization (GD’17), volume 10692 ofLNCS, pages 506–513. Springer, 2017.doi:10.1007/978-3-319-73915-1_ 39

    2017 doi

  13. [21]

    Area-universal and constrained rectangular layouts.SIAM Journal on Computing, 41(3):537–564, 2012.doi: 10.1137/110834032

    David Eppstein, Elena Mumford, Bettina Speckmann, and Kevin Verbeek. Area-universal and constrained rectangular layouts.SIAM Journal on Computing, 41(3):537–564, 2012.doi: 10.1137/110834032

    2012 doi

  14. [22]

    Planar and toroidal morphs made easier.Journal of Graph Algorithms and Applications, 27(2):95–118, 2023.doi:10.7155/jgaa.00616

    Jeff Erickson and Patrick Lin. Planar and toroidal morphs made easier.Journal of Graph Algorithms and Applications, 27(2):95–118, 2023.doi:10.7155/jgaa.00616

    2023 doi

  15. [23]

    Transversal structures on triangulations: A combinatorial study and straight-line drawings.Discrete Mathematics, 309(7):1870–1894, 2009.doi:10.1016/j.disc.2007.12

    Éric Fusy. Transversal structures on triangulations: A combinatorial study and straight-line drawings.Discrete Mathematics, 309(7):1870–1894, 2009.doi:10.1016/j.disc.2007.12. 093

    2009 doi

  16. [24]

    Ruben Gabriel and Robert R

    K. Ruben Gabriel and Robert R. Sokal. A new statistical approach to geographic variation analysis.Systematic Biology, 18(3):259–278, 1969.doi:10.2307/2412323

    1969 doi

  17. [25]

    Toroidalmaps: Schnyderwoods, orthogonalsurfaces and straight-line representations.Discrete & Computational Geometry, 51(1):67–131, 2014

    DanielGonçalvesandBenjaminLévêque. Toroidalmaps: Schnyderwoods, orthogonalsurfaces and straight-line representations.Discrete & Computational Geometry, 51(1):67–131, 2014. doi:10.1007/s00454-013-9552-7

    2014 doi

  18. [26]

    On finding the rectangular duals of planar triangular graphs.SIAM Journal on Computing, 22(6):1218–1226, 1993.doi:10.1137/0222072

    Xin He. On finding the rectangular duals of planar triangular graphs.SIAM Journal on Computing, 22(6):1218–1226, 1993.doi:10.1137/0222072

    1993 doi

  19. [27]

    Contact graphs of line segments are np-complete.Discrete Mathematics, 235(1- 3):95–106, 2001.doi:10.1016/S0012-365X(00)00263-6

    Petr Hlinený. Contact graphs of line segments are np-complete.Discrete Mathematics, 235(1- 3):95–106, 2001.doi:10.1016/S0012-365X(00)00263-6

    2001 doi

  20. [28]

    Representing graphs by disks and balls (a survey of recognition-complexityresults).Discrete Mathematics, 229(1-3):101–124, 2001.doi:10.1016/ S0012-365X(00)00204-1

    Petr Hlinený and Jan Kratochvíl. Representing graphs by disks and balls (a survey of recognition-complexityresults).Discrete Mathematics, 229(1-3):101–124, 2001.doi:10.1016/ S0012-365X(00)00204-1

    2001

  21. [29]

    Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems.Theoretical Computer Science, 172(1):175–193, 1997.doi:10

    Goos Kant and Xin He. Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems.Theoretical Computer Science, 172(1):175–193, 1997.doi:10. 1016/S0304-3975(95)00257-X

    1997

  22. [30]

    Combinatorial properties of triangle-free rectangle arrangements and the squarability problem

    Jonathan Klawitter, Martin Nöllenburg, and Torsten Ueckerdt. Combinatorial properties of triangle-free rectangle arrangements and the squarability problem. In Emilio Di Giacomo and Anna Lubiw, editors,Graph Drawing and Network Visualization (GD’15), pages 231–244. Springer, 20...

    2015 doi

  23. [31]

    Kontaktprobleme der konformen Abbildung.Berichte über die Verhandlungen der Sächsischen Akademie der Wiss

    Paul Koebe. Kontaktprobleme der konformen Abbildung.Berichte über die Verhandlungen der Sächsischen Akademie der Wiss. zu Leipzig. Math.-Phys. Klasse 88, pages 141–164, 1936

    1936

  24. [32]

    Rectangular duals of planar graphs.Networks, 15(2):145–157, 1985.doi:10.1002/net.3230150202

    Krzysztof Koźmiński and Edwin Kinnen. Rectangular duals of planar graphs.Networks, 15(2):145–157, 1985.doi:10.1002/net.3230150202

    1985 doi

  25. [33]

    Grid intersection and box intersection graphs on sur- faces

    Jan Kratochvíl and Teresa Przytycka. Grid intersection and box intersection graphs on sur- faces. In Franz J. Brandenburg, editor,Graph Drawing (GD’95), volume 1027 ofLNCS, pages 365–372. Springer, 1996.doi:10.1007/BFb0021820. 34 T. Biedl, P. Kindermann, and J. KlawitterRectan...

    1996 doi

  26. [34]

    On the characterization of rectangular duals

    Vinod Kumar and Krishnendra Shekhawat. On the characterization of rectangular duals. Notes on Number Theory and Discrete Mathematics, 30(1):141–149, 2024.doi:10.7546/ nntdm.2024.30.1.141-149

    2024

  27. [35]

    Leinwand

    Yen-Tai Lai and Sany M. Leinwand. A theory of rectangular dual graphs.Algorithmica, 5(4):467–483, 1990.doi:10.1007/BF01840399

    1990 doi

  28. [36]

    Computing a canon- ical polygonal schema of an orientable triangulated surface

    Francis Lazarus, Michel Pocchiola, Gert Vegter, and Anne Verroust. Computing a canon- ical polygonal schema of an orientable triangulated surface. In Diane L. Souvaine, ed- itor,Symposium on Computational Geometry (SoCG), pages 80–89. ACM, 2001.doi: 10.1145/378583.378630

    2001

  29. [37]

    Leinwand and Yen-Tai Lai

    Sany M. Leinwand and Yen-Tai Lai. An algorithm for building rectangular floor-plans. In 21st Design Automation Conference, pages 663–664, 1984.doi:10.1109/DAC.1984.1585874

    1984

  30. [38]

    Tessellation and visibility representations of maps on the torus.Discrete & Computational Geometry, 19:249–263, 1998.doi:10.1007/PL00009344

    Bojan Mohar and Pierre Rosenstiehl. Tessellation and visibility representations of maps on the torus.Discrete & Computational Geometry, 19:249–263, 1998.doi:10.1007/PL00009344

    1998 doi

  31. [39]

    Kobourov

    Sabrina Nusrat and Stephen G. Kobourov. The state of the art in cartograms.Computer Graphics Forum, 35(3):619–642, 2016.doi:10.1111/cgf.12932

    2016 doi

  32. [40]

    Graph theoretic representation of architectural arrangement.Architectural Research and Teaching, pages 161–172, 1973

    Philip Steadman. Graph theoretic representation of architectural arrangement.Architectural Research and Teaching, pages 161–172, 1973

    1973

  33. [41]

    Springer-Verlag, 1980

    John Stillwell.Classical topology and combinatorial group theory, volume 72 ofGraduate Texts in Mathematics. Springer-Verlag, 1980

    1980

  34. [42]

    On triangle cover contact graphs.Computational Geometry: Theory and Applications, 69:31– 38, 2018.doi:10.1016/J.COMGEO.2017.11.001

    ShaheenaSultana, IqbalHossain, SaidurRahman, NazmunNessaMoon, andTahsinaHashem. On triangle cover contact graphs.Computational Geometry: Theory and Applications, 69:31– 38, 2018.doi:10.1016/J.COMGEO.2017.11.001

    2018 doi

  35. [43]

    Tamassia and I

    R. Tamassia and I. Tollis. Representations of graphs on a cylinder.SIAM Journal of Discrete Mathematics, 4(1):139–149, 1991.doi:10.1137/0404014

    1991 doi

  36. [44]

    Depth-first search and linear graph algorithms.SIAM Journal on Computing, 1(2):146–160, 1972.doi:10.1137/0201010

    Robert Tarjan. Depth-first search and linear graph algorithms.SIAM Journal on Computing, 1(2):146–160, 1972.doi:10.1137/0201010

    1972 doi

  37. [45]

    Interval representations of planar graphs.Journal of Combinatorial Theory, Series B, 40(1):9–20, 1986.doi:10.1016/0095-8956(86)90061-4

    Carsten Thomassen. Interval representations of planar graphs.Journal of Combinatorial Theory, Series B, 40(1):9–20, 1986.doi:10.1016/0095-8956(86)90061-4

    1986 doi

  38. [46]

    On diagrams representing maps.Journal of the London Mathematical Society, 28(3):336–342, 1953.doi:10.1112/jlms/s1-28.3.336

    Peter Ungar. On diagrams representing maps.Journal of the London Mathematical Society, 28(3):336–342, 1953.doi:10.1112/jlms/s1-28.3.336

    1953 doi

  39. [47]

    Gary K. H. Yeap and Majid Sarrafzadeh. Sliceable floorplanning by graph dualization.SIAM Journal on Discrete Mathematics, 8(2):258–280, 1995.doi:10.1137/S0895480191266700

    1995 doi

Pith tools

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