Pith. sign in

REVIEW 4 major objections 5 minor 34 references

Representing Hypergraphs by Point-Line Incidences

T0 review · 4 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read Representing hypergraphs by points and straight lines is ∃R-hard for six of the eight natural decision variants, with polynomial-time algorithms only for restricted rank and degree bounds.

desk verdict A systematic and mostly convincing complexity map for point-line hypergraph drawing; three compressed proofs, including the load-bearing Lemma 4, need expansion, but the results are likely correct. read the letter →

arxiv 2411.13985 v4 pith:CQAR6QYX submitted 2024-11-21 cs.CG

Alexander Dobler , Stephen Kobourov , Debajyoti Mondal , Martin Nöllenburg This is my paper · ORCID
classification cs.CG
keywords hypergraphvisualizationpoint-lineincidence∃R-hardnessPappusconfigurationpseudolinestretchabilitymatroidrepresentabilitysegmentrepresentationcrossing-free
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

This paper studies whether a hypergraph can be visualized by mapping its vertices to points in the plane and its hyperedges to straight lines or line segments through the incident points, under rules that may or may not allow crossings and overlaps. Its central finding is that deciding the existence of such a representation is ∃R-hard for six of the eight natural variants, meaning these decision problems are at least as hard as solving systems of polynomial equations over the reals and therefore have no polynomial-time algorithm under standard complexity assumptions. The hardness holds even for hypergraphs of rank three and bounded maximum degree, with reductions built from the classical Pappus configuration. On the tractable side, the paper gives polynomial-time algorithms for rank-2 hypergraphs in all variants, for max-degree-2 hypergraphs in several settings, and a forbidden-subgraph characterization for rank-3 max-degree-2 segment representations; it also generalizes a known counterexample to a century-old claim by Steinitz on 3-regular hypergraphs.

What carries the argument

The Pappus gadget (the Pappus hypergraph) carries the argument: a rank-3 linear hypergraph with nine vertices and eight hyperedges whose three anchors must be collinear in every line or segment representation by Pappus's theorem (Theorem 3), yet which can be placed with its non-anchor vertices in an arbitrarily small disk to avoid any finite set of points and lines (Lemma 4). These two properties let reductions wire collinearity constraints into hypergraph instances sourced from pseudoline stretchability and matroid representability. The polynomial-time results rely on structural characterizations of line and segment arrangements, including permutation graphs for degree-2 hypergraphs and planar embeddings of vertex-edge incidence graphs.

What would settle it

Find a valid line or segment representation of the Pappus gadget whose three anchors are not collinear, or exhibit a finite set of points and lines that the Lemma 4 perturbation cannot avoid while keeping the anchors fixed; either would break the reductions that constitute the paper's hardness proofs.

Watch

Extended reading notes

Core claim

The paper proves ∃R-hardness for six of the eight decision problems asking whether a hypergraph has a line or segment representation, with or without strictness and with or without crossing-freedom. The main tool is the Pappus gadget, a nine-vertex, eight-hyperedge rank-3 linear hypergraph in which the anchors are forced to be collinear in every valid representation (Theorem 3), while remaining sufficiently flexible to avoid any finite set of unwanted incidences (Lemma 4). Reductions from pseudoline stretchability and matroid representability use this gadget to force collinearity and ordering constraints, yielding hardness for rank-3 max-degree-6 segment representations, rank-5 max-degree-2 segment representations, and strict variants with bounded rank and degree. The paper also identifies polynomial-time solvable cases, including all rank-2 hypergraphs, max-degree-2 hypergraphs for crossing-free line representations, and a complete characterization of rank-3 max-degree-2 segment representations via forbidden rigid triangles and rigid parallel 2-paths. Finally, it constructs 3-uniform 3-regular hypergraphs that require arbitrarily many bends, generalizing a counterexample to Steinitz's claim.

Load-bearing premise

The load-bearing premise is the combination of Theorem 3, that the Pappus gadget's anchors must be collinear in every representation, and Lemma 4, that the gadget can still be flexibly perturbed to avoid any finite set of unwanted points and lines; if that perturbation claim fails in degenerate configurations, the hardness reductions lose their correctness.

Editorial extensions

If this is right

  • Six of the eight representation-decision problems are ∃R-hard, so unless the complexity class ∃R collapses to P, none of those variants admits a polynomial-time recognition algorithm.
  • Practical visualization systems that work with points and lines for hyperedges cannot rely on exact polynomial-time representability checks; they must adopt heuristics or restrict to inputs like the tractable rank and degree classes identified here.
  • The polynomial-time cases are cleanly described: rank-2 hypergraphs are always representable in every variant, and a rank-3 max-degree-2 hypergraph has a segment representation exactly when it avoids the two forbidden rigid subhypergraphs.
  • The constructed 3-uniform 3-regular hypergraphs that require arbitrarily many bends give a quantitative refutation of Steinitz's classical claim, not just a single counterexample.

Reading between the lines

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

  • The Pappus-gadget approach may extend to polyline representations with a fixed number of bends, potentially proving ∃R-hardness for bend-limited hypergraph drawing variants beyond the 0-bend cases.
  • The open complexity gap at rank-4 max-degree-2 suggests the boundary between tractable and hard may be governed by whether three-point collinearity can be forced with only degree-3 vertices; a rank-4 gadget would likely settle it.
  • The Lemma 4 flexibility guarantee is a reusable tool: any geometric realizability problem that can host Pappus gadgets can inherit the same avoidance property, simplifying future reductions.
  • For designers of set-visualization tools, the rigid-triangle and rigid-parallel-2-path characterization offers a quick polynomial-time sanity check for whether a degree-2 hypergraph admits a segment representation, even though the general recognition problem is hard.
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

4 major / 5 minor

Summary. The paper studies the computational complexity of representing hypergraphs by point-line incidences, with hyperedges drawn as lines or segments, in strict or non-strict variants and with or without crossings. The main results are ∃R-hardness for six of the eight decision variants, obtained by reductions from pseudoline stretchability, matroid representability, and segment intersection graph recognition, using the Pappus configuration as a gadget that forces three anchor points to be collinear. The paper also provides polynomial-time algorithms and characterizations for restricted classes (rank-2, max-degree-2, and certain planar incidence graphs), and it generalizes a counterexample to a century-old claim of Steinitz about 3-uniform 3-regular hypergraphs with bends.

Significance. If the technical gaps identified below are repaired, the paper gives a clean and useful complexity landscape for a natural hypergraph visualization problem. The Pappus-gadget reductions are a reusable idea, the forbidden-substructure characterization of rank-3 max-degree-2 hypergraphs is a genuine algorithmic contribution, and the polynomial-time cases are well chosen. The paper is non-circular: all hardness reductions start from established ∃R-complete problems, and no target result is assumed. The main weakness is that several geometric correctness arguments are too compressed, and one of them, Lemma 4, is load-bearing for multiple hardness proofs.

major comments (4)
  1. [§3, Lemma 4] The proof of Lemma 4 does not establish the claimed avoidance for all hyperedge lines. After pushing p1 and p3 toward p2=p and rotating the base line {p1,p2,p3}, the six mixed lines {p1,p4,p8}, {p1,p5,p9}, {p2,p4,p7}, {p2,p6,p9}, {p3,p5,p7}, {p3,p6,p8} and the line {p4,p5,p6} are all determined continuously by the rotated configuration, but the proof only says that rotating the base line changes the slope of {p4,p5,p6}. It is not shown that for some nonempty interval of rotation angles all eight hyperedge lines avoid the finite point set A and all fixers avoid the finite line set B, nor is it shown that the configuration remains non-degenerate (e.g., p4≠p5, p1≠p3, and no mixed line passes through a non-incident anchor). Since Lemma 4 is invoked to place Pappus gadgets without unwanted incidences in Theorems 5, 10, and 17, this is a load-bearing gap. A rigorous argument should be supplied, for example by showing that the bad rotation angles form a finite set and that the limiting configuration can be chosen generically.
  2. [§4.2, Theorem 9] The entire correctness proof of Theorem 9 is the one-sentence assertion that, by construction, v1,...,vt must be collinear and appear in the correct order in any representation. This is the whole reduction, and it is not immediate: one must prove that the hyperedges {v_i, v_{i-1,1}, v_{i-1,2}, v_{i,1}, v_{i,2}} together with the two endpoint hyperedges force all v_i to lie on one common line, that they remain distinct, and that their order along that line is consistent with the pseudoline order up to reversal. The proof must also rule out unwanted incidences with the auxiliary vertices. As written, Theorem 9 and its corollary Corollary 16 are not established.
  3. [§6, Lemma 22] Lemma 22's proof contains a misattribution. The sentence 'If every hyperedge in the subhypergraph H2P is represented without a bend, then β({p'_7,p8,p9}) must pass through p7 due to Theorem 3' is not a consequence of Theorem 3 applied to H2P, because p7 is not a vertex of H2P. The intended implication holds if every hyperedge of H1P is bend-free, since then p7,p8,p9 are collinear and the full line β({p'_7,p8,p9}), which contains p8 and p9, also contains p7. The two 'at least one bend' conclusions need to be derived from the correct Pappus gadget. The conclusion may be recoverable, but the argument as written is not valid.
  4. [§5.2, Theorem 17] The hardness direction of Theorem 17 relies on the claim that the extended Pappus gadget forces the anchors to be collinear and that the gadgets can be placed with only infinitesimal disturbance. The text says that this follows by 'arguments similar to Lemma 4', but no such lemma is stated or proved for the extended gadget. Since Theorem 17 is one of the six claimed ∃R-hardness results, the proof should either state and prove an extended-gadget analogue of Lemma 4 or explain explicitly why the same perturbation argument applies in the strict crossing-free segment setting.
minor comments (5)
  1. [§5.2, Table 2 and Theorem 17] Theorem 17 states that the problem is ∃R-hard for rank-5 max-degree-10 hypergraphs, while Table 2 lists max-degree ≥ 12 for the same theorem. Please reconcile this discrepancy.
  2. [§6, Lemma 22 statement] The statement 'There is not-bend representation for H with t<2' should read 'There is no t-bend representation for H with t<2'.
  3. [§5.2, Theorem 21 proof] The proof contains typographical slips: 'we the selected set is S' should be 'we select the set S', and 'adjacent to both ep and Sq' should presumably be 'adjacent to both ep and eq'.
  4. [§4.2, Theorem 10] Theorem 10 invokes Lemma 4 in the context of strict segment representations, but Lemma 4 is stated for line representations. Please state explicitly why the avoidance lemma also applies when hyperedges are bounded segments and the representation is required to be strict.
  5. [§4.1, Theorem 5] In the '⇒' direction of Theorem 5, the phrase 'a contradiction, because we assumed that (α,β) is a line representation' could be expanded: the contradiction is that the hyperedge {d,x''} would contain x' although x' is not listed in that hyperedge. This is clear from context, but an explicit sentence would help the reader.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all hardness reductions start from established exogenous ∃R-hard problems and rely on external classical geometry (Pappus theorem), not on the paper's own claims.

full rationale

The paper's derivation chain is self-contained against external benchmarks. Theorem 5 reduces from Matroid Representability, citing Kim, de Mesmay, and Miltzow [25]; Theorems 8, 9, 10, and 17 reduce from pseudoline stretchability, citing Schaefer [30]; and Theorem 18 reduces from segment intersection graph recognition, citing Matousek [27]. These are independent, established ∃R-hardness results, so the hardness conclusions do not assume the target problems. The central geometric tool, the Pappus gadget, forces anchors to be collinear via Theorem 3, which the paper explicitly sources to Coxeter and Greitzer [8, Chapter 3.5], an external classical result rather than a self-citation. Lemma 4, which gives flexibility in placing Pappus gadgets, is argued by a continuity/perturbation construction, not by fitting a parameter to the target answer or by defining the conclusion into the premise; even if that argument has gaps in degenerate cases, that is a correctness risk, not circularity. The only self-references, [11] and [12], are the EuroCG and SOFSEM preliminary versions of this same work and are listed merely as Related Version notices; they are not load-bearing in any proof. The polynomial-time algorithms in Sections 4 and 5 are constructive and rely on standard graph-theoretic or geometric primitives, with no step that equates a prediction with an input by construction. Thus no load-bearing step reduces to its own inputs, and the paper is not circular.

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

No free parameters are fitted, because the paper is purely existential/combinatorial; epsilon values in Lemma 4 are arbitrary small quantities, not fitted constants. The axioms are standard projective geometry and previously established ∃R-hardness results. The only construction objects are finite hypergraph gadgets (Pappus gadget, extended Pappus gadget), which are not new physical entities and require no independent evidence beyond their stated combinatorial properties.

assumptions (5)
  • standard math Pappus theorem (classical theorem of projective geometry): for the Pappus configuration, the three anchors are collinear in every line/segment representation
    Invoked as Theorem 3; it is the core forcing mechanism in every Pappus-gadget reduction.
  • domain assumption Pseudoline stretchability is ∃R-hard (Schaefer 2009)
    Used as the reduction source for Theorems 8, 9, 10, 17, and Corollaries 15, 16.
  • domain assumption Matroid representability over R is ∃R-complete (Kim, de Mesmay, Miltzow 2024)
    Used as the reduction source for Theorem 5 and Corollary 6.
  • domain assumption Segment intersection graph recognition is ∃R-hard (Matousek 2014)
    Used as the reduction source for Theorem 18.
  • standard math Planar graph embedding and drawing algorithms run in polynomial time (e.g., Kaufmann-Wiese 2002)
    Used in the polynomial algorithms of Theorems 13, 14, 20, and 21.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Representing Hypergraphs by Point-Line Incidences." pith.science (2026). https://pith.science/paper/CQAR6QYX

@misc{pith2026241113985,
  author       = {Pith},
  title        = {Pith review of: Representing Hypergraphs by Point-Line Incidences},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CQAR6QYX}},
  note         = {Machine review of arXiv:2411.13985}
}
abstract

We consider hypergraph visualizations that represent vertices as points in the plane and hyperedges as curves passing through the points of their incident vertices. Specifically, we consider several different variants of this problem by (a) restricting the curves to be lines or line segments, (b) allowing two curves to cross if they do not share an element, or not; and (c) allowing two curves to overlap or not. We show $\exists\mathbb{R}$-hardness for six of the eight resulting decision problem variants and describe polynomial-time algorithms in some restricted settings. Lastly, we briefly touch on what happens if we allow the lines of the represented hyperedges to have bends - to this we generalize a counterexample to a long-standing result that was sometimes assumed to be correct.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 22 canonical work pages

  1. [1]

    Ramos, and Mary Czerwinski

    Basak Alper, Nathalie Henry Riche, Gonzalo A. Ramos, and Mary Czerwinski. Design study of linesets, a novel set visualization technique. IEEE Trans. Vis. Comput. Graph. , 17(12):2259--2267, 2011. https://doi.org/10.1109/TVCG.2011.186 doi:10.1109/TVCG.2011.186

    doi:10.1109/tvcg.2011.186 2011

  2. [2]

    Bilal Alsallakh, Luana Micallef, Wolfgang Aigner, Helwig Hauser, Silvia Miksch, and Peter J. Rodgers. The state-of-the-art of set visualization. Comput. Graph. Forum , 35(1):234--260, 2016. https://doi.org/10.1111/CGF.12722 doi:10.1111/CGF.12722

    doi:10.1111/cgf.12722 2016

  3. [3]

    The complexity of recognizing geometric hypergraphs

    Daniel Bertschinger, Nicolas El Maalouly, Linda Kleist, Tillmann Miltzow, and Simon Weber. The complexity of recognizing geometric hypergraphs. In Michael A. Bekos and Markus Chimani, editors, Proc. Graph Drawing (GD'23) , volume 14465 of LNCS , pages 163--179. Springer, 2023. https://doi.org/10.1007/978-3-031-49272-3\_12 doi:10.1007/978-3-031-49272-3\_12

    doi:10.1007/978-3-031-49272-3 2023

  4. [4]

    Path-based supports for hypergraphs

    Ulrik Brandes, Sabine Cornelsen, Barbara Pampel, and Arnaud Sallaberry. Path-based supports for hypergraphs. J. Discrete Algorithms , 14:248--261, 2012. https://doi.org/10.1016/J.JDA.2011.12.009 doi:10.1016/J.JDA.2011.12.009

    work page doi:10.1016/j.jda.2011.12.009 2012

  5. [5]

    van Kreveld, Henk Meijer, Bettina Speckmann, and Kevin Verbeek

    Kevin Buchin, Marc J. van Kreveld, Henk Meijer, Bettina Speckmann, and Kevin Verbeek. On planar supports for hypergraphs. J. Graph Algorithms Appl. , 15(4):533--549, 2011. https://doi.org/10.7155/JGAA.00237 doi:10.7155/JGAA.00237

    work page doi:10.7155/jgaa.00237 2011

  6. [6]

    Short plane supports for spatial hypergraphs

    Thom Castermans, Mereke van Garderen, Wouter Meulemans, Martin Nöllenburg, and Xiaoru Yuan. Short plane supports for spatial hypergraphs. J. Graph Algorithms Appl. , 23(3):463--498, 2019. https://doi.org/10.7155/jgaa.00499 doi:10.7155/jgaa.00499

    work page doi:10.7155/jgaa.00499 2019

  7. [7]

    Computing the girth of a planar graph in linear time

    Hsien - Chih Chang and Hsueh - I Lu. Computing the girth of a planar graph in linear time. SIAM J. Comput. , 42(3):1077--1094, 2013. https://doi.org/10.1137/110832033 doi:10.1137/110832033

    work page doi:10.1137/110832033 2013

  8. [8]

    Geometry revisited , volume 19

    Harold Scott Macdonald Coxeter and Samuel L Greitzer. Geometry revisited , volume 19. Mathematical Association of America, 1967

    work page 1967

Show all 34 references
  1. [9]

    Representations by contact and intersection of segments

    Hubert de Fraysseix and Patrice Ossona de Mendez. Representations by contact and intersection of segments. Algorithmica , 47(4):453--463, 2007. https://doi.org/10.1007/S00453-006-0157-X doi:10.1007/S00453-006-0157-X

    2007 doi

  2. [10]

    Representation of planar hypergraphs by contacts of triangles

    Hubert de Fraysseix, Patrice Ossona de Mendez, and Pierre Rosenstiehl. Representation of planar hypergraphs by contacts of triangles. In Seok - Hee Hong, Takao Nishizeki, and Wu Quan, editors, Proc. Graph Drawing (GD'07) , volume 4875 of LNCS , pages 125--136. Springer, 2007. ...

    2007 doi

  3. [11]

    Representing hypergraphs by point-line incidences

    Alexander Dobler, Stephen Kobourov, William J Lenhart, Tamara Mchedlidze, Martin N \"o llenburg, and Antonios Symvonis. Representing hypergraphs by point-line incidences. In 40th European Workshop on Computational Geometry, Ioannina, Greece , page 39, 2024

    2024

  4. [12]

    Kobourov, Debajyoti Mondal, and Martin N \" o llenburg

    Alexander Dobler, Stephen G. Kobourov, Debajyoti Mondal, and Martin N \" o llenburg. Representing hypergraphs by point-line incidences. In Rastislav Kr \' a lovic and Vera Kurkov \' a , editors, Proc. Theory and Practice of Computer Science (SOFSEM'25) , volume 15538 of LNCS ,...

    2025 doi

  5. [13]

    Testing bipartiteness of geometric intersection graphs

    David Eppstein. Testing bipartiteness of geometric intersection graphs. ACM Trans. Algorithms , 5(2):15:1--15:35, 2009. https://doi.org/10.1145/1497290.1497291 doi:10.1145/1497290.1497291

    2009

  6. [14]

    Hypergraph representation via axis-aligned point-subspace cover

    Oksana Firman and Joachim Spoerhase. Hypergraph representation via axis-aligned point-subspace cover. Discret. Math. Theor. Comput. Sci. , 27(2), 2025. https://doi.org/10.46298/DMTCS.11676 doi:10.46298/DMTCS.11676

    2025 doi

  7. [15]

    Embeddings of configurations

    Garret Flowers. Embeddings of configurations . PhD thesis, University of Victoria, 2015

    2015

  8. [16]

    Kobourov, Tamara Mchedlidze, Sergey Pupyrev, Torsten Ueckerdt, and Alexander Wolff

    Fabian Frank, Michael Kaufmann, Stephen G. Kobourov, Tamara Mchedlidze, Sergey Pupyrev, Torsten Ueckerdt, and Alexander Wolff. Using the metro-map metaphor for drawing hypergraphs. In Bures et al., editor, Proc. Conference on Current Trends in Theory and Practice of Computer S...

    2021 doi

  9. [17]

    David G. Glynn. On the representation of configurations in projective spaces. Journal of Statistical Planning and Inference , 86(2):443--456, May 2000. https://doi.org/10.1016/S0378-3758(99)00124-X doi:10.1016/S0378-3758(99)00124-X

    doi

  10. [18]

    A planar linear hypergraph whose edges cannot be represented as straight line segments

    Daniel Gon c alves. A planar linear hypergraph whose edges cannot be represented as straight line segments. Eur. J. Comb. , 30(1):280--282, 2009. https://doi.org/10.1016/J.EJC.2007.12.004 doi:10.1016/J.EJC.2007.12.004

    2009 doi

  11. [19]

    The drawing of configurations

    Harald Gropp. The drawing of configurations. In Franz - Josef Brandenburg, editor, Proc. Graph Drawing (GD'95) , volume 1027 of LNCS , pages 267--276. Springer, 1995. https://doi.org/10.1007/BFB0021810 doi:10.1007/BFB0021810

    1995 doi

  12. [20]

    Configurations and their realization

    Harald Gropp. Configurations and their realization. Discret. Math. , 174(1-3):137--151, 1997. https://doi.org/10.1016/S0012-365X(96)00327-5 doi:10.1016/S0012-365X(96)00327-5

    1997 doi

  13. [21]

    Configurations of Points and Lines

    Branko Gr\" u nbaum. Configurations of Points and Lines . American Mathematical Society, 2009

    2009

  14. [22]

    Kobourov, and Martin N \" o llenburg

    Ben Jacobsen, Markus Wallinger, Stephen G. Kobourov, and Martin N \" o llenburg. Metrosets: Visualizing sets as metro maps. IEEE Trans. Vis. Comput. Graph. , 27(2):1257--1267, 2021. https://doi.org/10.1109/TVCG.2020.3030475 doi:10.1109/TVCG.2020.3030475

    2021

  15. [23]

    Johnson and Henry O

    David S. Johnson and Henry O. Pollak. Hypergraph planarity and the complexity of drawing venn diagrams. J. Graph Theory , 11(3):309--325, 1987. https://doi.org/10.1002/JGT.3190110306 doi:10.1002/JGT.3190110306

    1987 doi

  16. [24]

    Embedding vertices at points: Few bends suffice for planar graphs

    Michael Kaufmann and Roland Wiese. Embedding vertices at points: Few bends suffice for planar graphs. J. Graph Algorithms Appl. , 6(1):115--129, 2002. https://doi.org/10.7155/JGAA.00046 doi:10.7155/JGAA.00046

    2002 doi

  17. [25]

    Representing matroids over the reals is \( \) \( r \) -complete

    Eun Jung Kim, Arnaud de Mesmay, and Tillmann Miltzow. Representing matroids over the reals is \( \) \( r \) -complete. Discret. Math. Theor. Comput. Sci. , 26(2), 2024. https://doi.org/10.46298/DMTCS.10810 doi:10.46298/DMTCS.10810

    2024 doi

  18. [26]

    The application of determining sets to projective configurations

    William Kocay and Ryan Szypowski. The application of determining sets to projective configurations. Ars Combinatoria , 53:193--208, 1999

    1999

  19. [27]

    Intersection graphs of segments and R

    Jir \' Matousek. Intersection graphs of segments and R . CoRR , abs/1406.2636, 2014. https://arxiv.org/abs/1406.2636 arXiv:1406.2636

    2014 arXiv

  20. [28]

    McConnell and Jeremy P

    Ross M. McConnell and Jeremy P. Spinrad. Modular decomposition and transitive orientation. Discret. Math. , 201(1-3):189--241, 1999. https://doi.org/10.1016/S0012-365X(98)00319-7 doi:10.1016/S0012-365X(98)00319-7

    1999 doi

  21. [29]

    How to draw a hypergraph

    Erkki Mäkinen. How to draw a hypergraph. Int. J. Computer Math. , 34(3--4):177--185, 1990. https://doi.org/10.1080/00207169008803875 doi:10.1080/00207169008803875

    1990 doi

  22. [30]

    Complexity of some geometric and topological problems

    Marcus Schaefer. Complexity of some geometric and topological problems. In David Eppstein and Emden R. Gansner, editors, Proc. Graph Drawing (GD'09) , volume 5849 of LNCS , pages 334--344. Springer, 2009. https://doi.org/10.1007/978-3-642-11805-0_32 doi:10.1007/978-3-642-11805-0_32

    2009 doi

  23. [31]

    Peter W. Shor. Stretchability of pseudolines is NP -hard. In Peter Gritzmann and Bernd Sturmfels, editors, Proc. Applied Geometry And Discrete Mathematics (DIMACS'90) , volume 4 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science , pages 531--554. DIMACS/...

    1990 doi

  24. [32]

    \"U ber die Construction der Configurationen \(n_3\)

    Ernst Steinitz. \"U ber die Construction der Configurationen \(n_3\) . PhD thesis, Breslau, 1894

  25. [33]

    Swaminathan and Donald K

    R. Swaminathan and Donald K. Wagner. On the consecutive-retrieval problem. SIAM J. Comput. , 23(2):398--414, 1994. https://doi.org/10.1137/S0097539792235487 doi:10.1137/S0097539792235487

    1994 doi

  26. [34]

    Kobourov, and Martin N \" o llenburg

    Markus Wallinger, Ben Jacobsen, Stephen G. Kobourov, and Martin N \" o llenburg. On the readability of abstract set visualizations. IEEE Trans. Vis. Comput. Graph. , 27(6):2821--2832, 2021. https://doi.org/10.1109/TVCG.2021.3074615 doi:10.1109/TVCG.2021.3074615

    2021

Pith tools

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