Pith. sign in

REVIEW 3 major objections 5 minor 33 references

Representing Graphs and Hypergraphs by Touching Polygons in 3D

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 Every graph with minimum degree 3—and hence every graph after adding dummy neighbors—can be drawn as convex polygons in 3D that touch only at shared corners.

desk verdict The universal construction is real but the write-up is too terse; the deletion-step worry the reader flagged actually closes with a one-line extreme-point argument, so this deserves refereeing, not rejection. read the letter →

arxiv 1908.08273 v3 pith:CC5CXDB6 submitted 2019-08-22 cs.CG

William Evans , Pawe{l} Rzążewski , Noushin Saeedi , Chan-Su Shin , Alexander Wolff This is my paper · ORCID
classification cs.CG MSC 05C6205C6568U05
keywords contactrepresentationconvexpolygons3DgraphdrawinghypergraphsSteinertriplesystemsquadruplegriddrawingsexistentialtheoryofthereals
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

Contact representations encode a graph by geometric objects that touch exactly when the corresponding vertices are adjacent. This paper proves that such representations exist in three dimensions using convex polygons: starting from a contact representation of the complete graph $K_n$, one removes the corner point for each missing edge, which yields a representation of every graph whose vertices all have degree at least 3; adding dummy vertices extends this to every graph. The general construction uses exponentially large coordinates, so the paper also builds polynomial-size grid representations for bipartite, 1-planar cubic, and subcubic graphs. On the hypergraph side, representing the dual—vertices as points and hyperedges as polygons—is much more restrictive: some small regular hypergraphs, including Steiner quadruple systems, are shown to be non-realizable, while the two smallest Steiner triple systems are realized with triangles.

What carries the argument

The load-bearing construction is an arrangement of $n$ lines in the $xy$-plane with exponentially decreasing gaps between consecutive intersection points along each line. Lifting each intersection point $p_{i,j}$ to height $\min(i,j)$ and taking the convex hull of the lifted points on each line produces the polygon $P_i$ in the vertical plane over line $i$. The halving condition does two jobs: it forces the boundary angles of each polygon to stay below $\pi$, so the polygon is simple, and it controls the vertical overlap of polygons whose projections meet, so $P_i$ and $P_j$ touch only at $p_{i,j}$. Deleting $p_{i,j}$ for each non-edge is the step that extends the complete-graph representation to arbitrary graphs of minimum degree 3.

What would settle it

Construct the line arrangement of Lemma 2.2 for a small graph such as $K_5$ with one edge removed, delete the point for the missing edge, and test whether the two corresponding convex hulls intersect anywhere outside that point; an intersection would refute Corollary 2.4.

Watch

Extended reading notes

Core claim

The central discovery is Corollary 2.4: every graph with minimum vertex-degree 3 admits a contact representation by nondegenerate convex polygons in 3D, where two polygons share a corner point exactly when the corresponding vertices are adjacent and each corner point represents one edge. The proof first realizes the complete graph $K_n$. Each vertex $i$ becomes the convex hull of points placed on a line $\ell_i$ in the $xy$-plane, with the intersection point $p_{i,j}$ of $\ell_i$ and $\ell_j$ lifted to height $\min(i,j)$; polygon $i$ therefore lies in the vertical plane over $\ell_i$. The lines are arranged so distances between consecutive intersection points halve, which keeps each polygon simple and separates non-adjacent polygons vertically. For a non-edge $\{i,j\}$, removing the point $p_{i,j}$ before taking convex hulls is claimed to separate the two polygons. For hypergraphs, the paper shows that the two smallest Steiner triple systems can be drawn with triangles, while no Steiner quadruple system can be drawn with convex quadrilaterals and none of size at least 20 can be drawn with arbitrary quadrilaterals.

Load-bearing premise

The construction assumes that deleting the corner point for a non-edge separates the two polygons vertically, so that wherever their projections still overlap the two polygons occupy different heights.

Editorial extensions

If this is right

  • Every graph with minimum degree 3, and hence every graph after adding dummy neighbors, can be realized by convex polygons in 3D; the question of whether coordinates can be kept polynomial for all graphs remains open.
  • Bipartite graphs admit linear-time constructions on grids of volume $O(n^4)$; 1-planar cubic graphs use volume $O(n^2)$, and all cubic graphs use volume $O(n^3)$.
  • Squares of even cycles can be represented by unit squares with a constant ratio between longest and shortest quadrilateral edge.
  • No Steiner quadruple system is realizable by convex quadrilaterals, and any such system with at least 20 vertices is not realizable by quadrilaterals at all.
  • Recognizing intersection graphs of line segments in 3D is complete for the existential theory of the reals, so the recognition problem for this class is computationally hard.

Reading between the lines

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

  • Because the halving condition forces the general construction's coordinates to grow super-polynomially, a positive answer to the paper's open problem about polynomial volume would need a fundamentally different construction.
  • The same vertical-separation idea—giving each contact a low height for one polygon and a high height for the other—may transfer to other 3D contact models, such as the monotone polygonal curves mentioned in the conclusion.
  • The counting argument used against Steiner quadruple systems suggests a general density threshold: a $k$-uniform hypergraph with too many edges through each vertex cannot have a non-crossing polygon drawing, because the local contact graph around any vertex would become non-planar.
  • Running the deletion construction on small graphs, for example $K_5$ with one edge removed, would provide a concrete check of the separation step that carries the universal graph result.
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.

Referee Report

3 major / 5 minor

Summary. The manuscript studies contact representations of graphs and hypergraphs by non-intersecting convex polygons in 3D, where two polygons touch only at shared corner points. Its main positive claim is that every graph with minimum vertex degree 3 admits such a representation (Corollary 2.4), obtained by starting from a contact representation of K_n and deleting the points corresponding to non-edges. The paper also gives polynomial-volume constructions for bipartite, 1-planar cubic, cubic, and squares-of-cycles graph classes, shows that recognizing 3D segment intersection graphs is ∃R-complete, and proves several representability and non-representability results for Steiner systems: the two smallest Steiner triple systems are representable, while Steiner quadruple systems are not representable with convex quadrilaterals and sufficiently large ones are not representable with arbitrary quadrilaterals.

Significance. If the central construction can be made rigorous, the result that every graph with minimum degree 3 admits a contact representation by convex polygons in 3D is a strong and surprising contribution: it shows that this geometric contact model is universal for a broad graph class. The paper is also valuable for its explicit constructions for special graph classes (bipartite, subcubic, 1-planar cubic, squares of cycles) and for its negative results on Steiner quadruple systems, which give interesting limits on what touching-polygon representations can express. The use of known tools (Petersen's theorem, Schnyder's algorithm, Dey–Edelsbrunner counting) and the clarity of the exposition are assets; however, no machine-checked proofs or reproducible code accompany the manuscript, and the main constructive proof currently rests on under-specified geometric arguments.

major comments (3)
  1. [Lemma 2.2 (p. 6)] The proof of Lemma 2.2 is not a complete existence proof of the line arrangement. When line l_i is introduced by rotating a copy of l_{i-1} about p_{i-1,i}, the order property (A1) for l_i includes intersections with lines l_{i+1},...,l_n that have not yet been constructed, so the proof cannot verify at that stage that l_i intersects those future lines in the required order; moreover, the subsequent rotations that create those future lines can change the distances between the intersection points on l_i, yet the argument asserts without justification that 'all inequalities in (A2) are satisfied' throughout. A rigorous induction would need to specify how future lines are placed so as to respect all previously fixed orders and distance bounds, or the authors should cite or prove an alternative existence result. Since Theorem 2.3 builds every polygon on this arrangement, this gap affects the main construction.
  2. [Corollary 2.4 (p. 7)] The deletion step in Corollary 2.4 does not, as written, establish that P_i and P_j are disjoint for a non-edge {i,j}. For i<j, removing p_{i,j} from both vertex sets does not remove the projection point from either convex hull: P_i typically retains points at height z=i on both sides of p_{i,j} along l_i, and P_j retains lower-chain points on both sides of p_{j,i} along l_j, so both polygons may still have nonempty vertical sections over the same xy-location. The proof only says to 'just remove the point p_{i,j}', and the final sentence of Theorem 2.3 does not apply because p_{i,j} is no longer a common vertex. A complete argument must show that at every such projection the upper z-extent of P_i is strictly below i and the lower z-extent of P_j is strictly above i (or that the projection lies outside one of the hulls), using the exponential distance decay (A2). Without this separation argument the universal claim 'every graph with minimum vertex-degree 3' is not supported.
  3. [Theorem 3.6 (Section 3.1)] The proof of Theorem 3.6 is a sketch rather than a complete proof. The authors state that they 'need to redo' the Dey–Edelsbrunner counting lemma taking lower-order terms into account, but the redo is not provided; the subsequent claims that intersecting the split triangles with a small sphere around a vertex yields a planar graph with (n-1)(n-2)/3 edges, and at least (n-1)(n-2)/6 edges in the non-convex case, presuppose an unstated choice of the triangulation and an unstated verification that the resulting triangles have no non-trivial intersections. The thresholds n>8 and n≥20 are asserted without the derivation. Since Theorem 3.6 is the main negative result for Steiner quadruple systems, this is a load-bearing gap in the hypergraph part of the paper.
minor comments (5)
  1. [After Corollary 2.4 (p. 8)] The remark on making the polygons strictly convex is unclear: if the z-coordinate of every point p_{i,j} is decreased, then adjacent polygons no longer share p_{i,j}; please clarify which points are moved and how the contact property is preserved.
  2. [Theorem 2.1 proof (p. 5)] The name 'Schaeffer' appears where 'Schaefer' is meant; reference [17] also contains a corrupted author name that should be repaired.
  3. [Proposition 3.1 (p. 20)] The proof for S(2,3,9) relies on several assertions stated as 'it is easy to see' and on inspection of Fig. 16; the choice β=45° and the lifting of P by 1/10 should be justified numerically or by a short convexity argument.
  4. [Theorem 2.12 (p. 18)] The case C_5^2 = K_5 is left as an exercise; since the paper otherwise gives explicit constructions, please include a short description or a citation for this base case.
  5. [Lemma 2.2 (p. 6)] The proof would be much easier to follow if, at each incremental step, the authors stated explicitly which of the inequalities (1)–(4) is being enforced with equality and how the previously established inequalities remain invariant under the rotation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the construction is self-contained and external citations are independent.

full rationale

This is a constructive existence proof with no fitted parameters, empirical predictions, or data-derived outputs. The main chain (Lemma 2.2, Theorem 2.3, Corollary 2.4) builds a contact representation of K_n from an explicitly constructed line arrangement and then attempts to specialize to arbitrary minimum-degree-3 graphs by deleting the points p_{i,j} for non-edges. That specialization does not assume the target graph's representation as an input; it starts from a stronger universal object (K_n) and deletes information, so there is no self-definitional or fitted-input circularity. The cited external results (Petersen's theorem, Schnyder's grid drawing, the Dey-Edelsbrunner counting lemma, and Ossona de Mendez's poset embedding) are genuinely independent and are not by the present authors. The only self-citations are to the authors' own GD 2019 preliminary version [13] and to related work [2], neither of which is load-bearing for the main construction. The possible gap in Corollary 2.4, namely that deleting p_{i,j} may not separate the two convex hulls at that xy-projection, is a proof-correctness concern about a concrete geometric separation claim, not a circularity, because the conclusion is not assumed in the premises. The hypergraph results similarly rely on external combinatorial facts and explicit case analysis. Accordingly the paper receives a circularity score of 0.

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

The central graph constructions use no fitted or empirical parameters; the free parameters listed are hand-chosen constants for a specific small hypergraph drawing. The proof relies on standard external theorems for matchings and planar drawings, plus one counting bound that the paper says it reworks but does not fully present. No new geometric primitives or entities are introduced beyond the polygons and points that define the model.

free parameters (3)
  • Rotation angle beta for the S(2,3,9) drawing = 45 degrees
    Chosen by hand in Proposition 3.1 to keep the green and blue triangles interior-disjoint; no general rule fixes its value.
  • Scale factor for the inner triangle in S(2,3,9) = 1/5
    Chosen ad hoc in Proposition 3.1 so that the constructed triangles avoid one another; the proof only requires a sufficiently small factor.
  • Lift constant for vertex 7 in S(2,3,9) = 1/10 unit
    Introduced in Proposition 3.1 to place vertex 7 just above a computed point P while staying below a plane; the exact value is a hand-picked small number.
assumptions (3)
  • standard math Petersen's theorem: every 2-edge-connected cubic graph has a perfect matching.
    Invoked in Lemma 2.9 to split a cubic graph into a perfect matching and disjoint cycles.
  • standard math Schnyder's algorithm draws 3-connected planar graphs straight-line on a grid of linear size.
    Used in Theorems 2.8 and 2.10 to draw medial and floorplan graphs on polynomial-size grids.
  • domain assumption A reworked Dey-Edelsbrunner counting bound for triangles spanned by n points in 3D, with lower-order terms included.
    Theorem 3.6 states 'we need to redo their proof taking lower-order terms into account' but does not provide the redo; the sphere-intersection planarity argument is a sketch rather than a full derivation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Representing Graphs and Hypergraphs by Touching Polygons in 3D." pith.science (2026). https://pith.science/paper/CC5CXDB6

@misc{pith2026190808273,
  author       = {Pith},
  title        = {Pith review of: Representing Graphs and Hypergraphs by Touching Polygons in 3D},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CC5CXDB6}},
  note         = {Machine review of arXiv:1908.08273}
}
read the original abstract

Contact representations of graphs have a long history. Most research has focused on problems in 2D, but 3D contact representations have also been investigated, mostly concerning fully-dimensional geometric objects such as spheres or cubes. In this paper we study contact representations with convex polygons in 3D. We show that every graph admits such a representation. Since our representations use super-polynomial coordinates, we also construct representations on grids of polynomial size for specific graph classes (bipartite, subcubic). For hypergraphs, we represent their duals, that is, each vertex is represented by a point and each edge by a polygon. We show that even regular and quite small hypergraphs do not admit such representations. On the other hand, the two smallest Steiner triple systems can be represented.

Figures

Figures reproduced from arXiv: 1908.08273 by the authors.

Figure 1
Figure 1. Original segments and frame segments [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Left: Placement of order segments (thin lines). Original segments [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Construction of `4 in the proof of Lemma 2.2. pi,1 pi,i−2 pi,i−1 pi,i+1 pi,n 1 i − 1 i i − 2 [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (14 more)
Figure 5
Figure 5. Figure 5: A contact representation of K8,8 using a toroidal grid. to property (ii) of our lead polygon. Using evenly spaced vertices on a half circle as our lead, we get a representation on a toroidal grid1 of size |B| × (2|A| − 2) (note that our representation uses the inner ha…
Figure 6
Figure 6. Figure 6: Top view of a contact representation of K8,16 on the integer grid. z [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]
Figure 7
Figure 7. Figure 7: Side view of a contact representation of [PITH_FULL_IMAGE:figures/full_fig_p010_7.png]
Figure 8
Figure 8. Figure 8: A contact representation of K3,3 with unit equilateral triangles. coordinates 0, 1/2, 1, and are centered at the z-axis. The topmost triangle is right above the bottommost one, whereas the middle triangle is rotated by an angle β. In the projection on the xy-plane, all…
Figure 9
Figure 9. Figure 9: 1-plane cubic graphs admit compact triangle contact representations. [PITH_FULL_IMAGE:figures/full_fig_p012_9.png]
Figure 10
Figure 10. Figure 10: left: graphs G (with a crossing on the outer face) and G0 med; center: straight-line drawing of G0 med; right: resulting 3D representation of G (numbers are z-coordinates). the outer face of G0 med). Triangles that share an edge in the projection are in￾cident to the …
Figure 11
Figure 11. Figure 11: Representing a 2-edge-connected cubic graph [PITH_FULL_IMAGE:figures/full_fig_p014_11.png]
Figure 12
Figure 12. Figure 12: Constructing the floorplan H of a general cubic graph triangle apexes. This also determines which vertices of Gi are represented by chord-based triangles. If applying Petersen’s theorem to Gi gives rise to a single cycle, we consider the chord (which will be drawn at …
Figure 13
Figure 13. Figure 13: Representation of a bridge b = ac depending on the types of its feet see [PITH_FULL_IMAGE:figures/full_fig_p017_13.png]
Figure 14
Figure 14. Figure 14: Representing squares of cycles: we build a contact representation [PITH_FULL_IMAGE:figures/full_fig_p019_14.png]
Figure 15
Figure 15. Figure 15: The Fano plane and a drawing using touching triangles in 3D [PITH_FULL_IMAGE:figures/full_fig_p021_15.png]
Figure 16
Figure 16. Figure 16: Partial drawing of the Steiner triple system [PITH_FULL_IMAGE:figures/full_fig_p022_16.png]
Figure 17
Figure 17. Figure 17: 3D contact representation of the Steiner triple system [PITH_FULL_IMAGE:figures/full_fig_p023_17.png]
Figure 18
Figure 18. Figure 18: The second smallest discrete projective plane [PITH_FULL_IMAGE:figures/full_fig_p027_18.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 13 canonical work pages

  1. [1]

    M. J. Alam.Contact Representations of Graphs in 2D and 3D. PhD thesis, The University of Arizona, 2015

    work page 2015

  2. [2]

    M. J. Alam, W. Evans, S. G. Kobourov, S. Pupyrev, J. Toeniskoetter, and T. Ueckerdt. Contact representations of graphs in 3D. In F. Dehne, J.-R. Sack, and U. Stege, editors,Proc. Algorithms and Data Structures Symposium (WADS’15), volume 9214 ofLNCS, pages 14–27, 2015.doi: 10.1007/978-3-319-21840-3\_2

    doi:10.1007/978-3-319-21840-3 2015

  3. [3]

    M. J. Alam, M. Kaufmann, and S. G. Kobourov. On contact graphs with cubes and proportional boxes. In R. M. Freivalds, G. Engels, and B. Cata- nia, editors, Proc. 42nd Conf. Current Trends Theory & Pract. Comput. Sci. (SOFSEM’16), volume 9587 ofLNCS, pages 107–120. Springer, 2016. doi:10.1007/978-3-662-49192-8\_9

    work page doi:10.1007/978-3-662-49192-8 2016

  4. [4]

    Brandes, S

    U. Brandes, S. Cornelsen, B. Pampel, and A. Sallaberry. Path-based sup- ports for hypergraphs. J. Discrete Algorithms, 14:248–261, 2012. doi: 10.1016/j.jda.2011.12.009

    doi:10.1016/j.jda.2011.12.009 2012

  5. [5]

    Bremner, W

    D. Bremner, W. Evans, F. Frati, L. Heyer, S. G. Kobourov, W. J. Lenhart, G. Liotta, D. Rappaport, and S. H. Whitesides. On representing graphs by touching cuboids. In W. Didimo and M. Patrignani, editors,Proc. Int. Symp. Graph Drawing (GD’12), volume 7704 of LNCS, pages 187–198,

    work page

  6. [6]

    Buchin, M

    K. Buchin, M. J. van Kreveld, H. Meijer, B. Speckmann, and K. Verbeek. On planar supports for hypergraphs.J. Graph Algorithms Appl., 15(4):533– 549, 2011. doi:10.7155/jgaa.00237

    doi:10.7155/jgaa.00237 2011

  7. [7]

    J. F. Canny. Some algebraic and geometric computations in PSPACE. In J.Simon, editor,Proc. 20th Ann. ACM Symp. Theory Comput. (STOC’88), pages 460–467, 1988.doi:10.1145/62212.62257

    arXiv 1988

  8. [8]

    Cardinal, S

    J. Cardinal, S. Felsner, T. Miltzow, C. Tompkins, and B. Vogtenhuber. Intersection graphs of rays and grounded segments.J. Graph Algorithms Appl., 22(2):273–295, 2018.doi:10.7155/jgaa.00470

    doi:10.7155/jgaa.00470 2018

Show all 33 references
  1. [9]

    Carmesin

    J. Carmesin. Embedding simply connected 2-complexes in 3-space – I. A Kuratowski-type characterisation. ArXiv report, 2019. URL: http: //arxiv.org/abs/1709.04642

    2019 arXiv

  2. [10]

    T. K. Dey and H. Edelsbrunner. Counting triangle crossings and halv- ing planes. Discrete Comput. Geom., 12(3):281–289, 1994.doi:10.1007/ BF02574381

    1994

  3. [11]

    Diks and P

    K. Diks and P. Stańczyk. Perfect matching for biconnected cubic graphs in O(n log2n) time. In J. van Leeuwen, A. Muscholl, D. Peleg, J. Poko- rný, and B. Rumpe, editors,Proc. 36th Conf. Current Trends Theory & Evans et al. 29 Pract. Comput. Sci. (SOFSEM’10), volume 5901 ofLNCS...

    2010 doi

  4. [12]

    Erickson and S

    J. Erickson and S. Kim. Arbitrarily large neighborly families of congru- ent symmetric convex 3-polytopes. In A. Bezdek, editor,Discrete Geome- try, volume 253 ofPure and Applied Mathematics, pages 267–278. Marcel Dekker, New York, 2003. In Honor of W. Kuperberg’s 60th Birthday

    2003

  5. [13]

    W. S. Evans, P. Rz1ażewski, N. Saeedi, C. Shin, and A. Wolff. Represent- ing graphs and hypergraphs by touching polygons in 3d. In D. Archam- bault and C. D. Tóth, editors,Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Prague, Czech Republic, S...

    2019 doi

  6. [14]

    Felsner and M

    S. Felsner and M. C. Francis. Contact representations of planar graphs with cubes. In F. Hurtado and M. J. van Kreveld, editors, Proc. 27th Ann. Symp. Comput. Geom. (SoCG’11), pages 315–320. ACM, 2011.doi: 10.1145/1998196.1998250

    2011

  7. [15]

    H. Gropp. The drawing of configurations. In F. J. Brandenburg, editor, Proc. Int. Symp. Graph Drawing (GD’95), volume 1027 ofLNCS, pages 267–276. Springer, 1996.doi:10.1007/BFb0021810

    1996 doi

  8. [16]

    Hliněný and J

    P. Hliněný and J. Kratochvíl. Representing graphs by disks and balls (a survey of recognition-complexity results). Discrete Mathematics, 229(1– 3):101–124, 2001.doi:10.1016/S0012-365X(00)00204-1

    2001 doi

  9. [17]

    Ho0+1+1+1sten and W

    S. Ho0+1+1+1sten and W. D. Morris. The order dimension of the complete graph. Discrete Math., 201(1):133–139, 1999. doi:10.1016/ S0012-365X(98)00315-X

    1999

  10. [18]

    D. S. Johnson and H. O. Pollak. Hypergraph planarity and the complexity of drawing Venn diagrams.J. Graph Theory, 11(3):309–325, 1987.doi: 10.1002/jgt.3190110306

    1987 doi

  11. [19]

    P. Koebe. Kontaktprobleme der konformen Abbildung.Berichte über die Verhandlungen der Sächsischen Akad. der Wissen. zu Leipzig. Math.-Phys. Klasse, 88:141–164, 1936

    1936

  12. [20]

    Kratochvíl and J

    J. Kratochvíl and J. Matoušek. Intersection graphs of segments.J. Comb. Theory, Ser. B, 62(2):289–315, 1994.doi:10.1006/jctb.1994.1071

    1994

  13. [21]

    Matoušek

    J. Matoušek. Intersection graphs of segments and∃R. ArXiv report, 2014. URL: http://arxiv.org/abs/1406.2636

    2014 arXiv

  14. [22]

    Ossona de Mendez

    P. Ossona de Mendez. Realization of posets.J. Graph Algorithms Appl., 6(1):149–153, 2002.doi:10.7155/jgaa.00048. 30 Representing Graphs and Hypergraphs by Polygons in 3D

    2002 doi

  15. [23]

    Petersen

    J. Petersen. Die Theorie der regulären graphs. Acta Math., 15:193–220,

  16. [24]

    Schaefer

    M. Schaefer. Complexity of some geometric and topological problems. In D. Eppstein and E. R. Gansner, editors,Proc. 17th Int. Symp. Graph Drawing (GD’09), volume 5849 ofLNCS, pages 334–344. Springer, 2010. doi:10.1007/978-3-642-11805-0\_32

    2010 doi

  17. [25]

    Schnyder

    W. Schnyder. Embedding planar graphs on the grid. InProc. 1st ACM- SIAM Symp. Discrete Algorithms (SODA’90), pages 138–148, 1990. URL: https://dl.acm.org/citation.cfm?id=320176.320191

    1990

  18. [26]

    Thomassen

    C. Thomassen. Interval representations of planar graphs.J. Combin. The- ory Ser. B, 40(1):9–20, 1986.doi:10.1016/0095-8956(86)90061-4

    1986 doi

  19. [27]

    Convexpolygonintersectiongraphs

    E.J.vanLeeuwenandJ.vanLeeuwen. Convexpolygonintersectiongraphs. In U. Brandes and S. Cornelsen, editors, Proc. 18th Int. Symp. Graph Drawing (GD’10), volume 6502 ofLNCS, pages 377–388. Springer, 2011. doi:10.1007/978-3-642-18469-7\_35

    2011 doi

  20. [28]

    E. W. Weisstein. Steiner quadruple system. From MathWorld – A Wolfram Web Resource. Accessed 2019-08-20. URL:http://mathworld.wolfram. com/SteinerQuadrupleSystem.html

    2019

  21. [29]

    E. W. Weisstein. Steiner triple system. From MathWorld – A Wolfram Web Resource. Accessed 2019-08-20. URL:http://mathworld.wolfram. com/SteinerTripleSystem.html

    2019

  22. [30]

    Westbrook and R

    J. Westbrook and R. E. Tarjan. Maintaining bridge-connected and bi- connected components on-line. Algorithmica, 7(1):433–464, 1992. doi: 10.1007/BF01758773

    1992 doi

  23. [31]

    A. A. Zykov. Hypergraphs.Uspekhi Mat. Nauk, 29(6):89–154, 1974.doi: 10.1070/RM1974v029n06ABEH001303

    1974 doi

  24. [1891]

    doi:10.1007/BF02392606

    doi

  25. [2012]

    doi:10.1007/978-3-642-36763-2\_17

    doi

Pith tools

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