Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Representing Hypergr ...
Article

Representing Hypergraphs by Point-Line Incidences

Alexander Dobler ORCID (1), Stephen Kobourov ORCID (2), Debajyoti Mondal ORCID (3), Martin Nöllenburg ORCID (1)
(1) TU Wien [TUW]
(2) Technical University of Munich [TUM]
(3) University of Saskatchewan [USASK]
Download article
Open on arXiv
Submitted on
June 16, 2025
Accepted on
June 25, 2026
Published on
August 19, 2026
Last modified on
August 19, 2026
Volume 28
vol. 28:3
Combinatorics
DOI
10.46298/dmtcs.15876
License
Attribution 4.0 International (CC BY 4.0)
Indicators
117
Views
82
Downloads

Representing Hypergraphs by Point-Line Incidences

Alexander Dobler ORCID (1), Stephen Kobourov ORCID (2), Debajyoti Mondal ORCID (3), Martin Nöllenburg ORCID (1)
(1) TU Wien [TUW]
(2) Technical University of Munich [TUM]
(3) University of Saskatchewan [USASK]
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. 24 pages, 12 figures
Keywords
  • Computational Geometry
Preview
Loading PDF preview...
References

  1. B. Alper, N. H. Riche, G. A. Ramos, and M. Czerwinski. Design study of linesets, a novel set visualization technique. IEEE Trans. Vis. Comput. Graph., 17(12):2259-2267, 2011.

    DOI : 10.1109/tvcg.2011.186

  2. B. Alsallakh, L. Micallef, W. Aigner, H. Hauser, S. Miksch, and P. J. Rodgers. The state-of-the-art of set visualization. Comput. Graph. Forum, 35(1):234-260, 2016.

    DOI : 10.1111/cgf.12722

  3. D. Bertschinger, N. E. Maalouly, L. Kleist, T. Miltzow, and S. Weber. The complexity of recognizing geometric hypergraphs. In M. A. Bekos and M. Chimani, editors, Proc. Graph Drawing (GD'23), volume 14465 of LNCS, pages 163-179. Springer, 2023.

    DOI : 10.1007/978-3-031-49272-3

  4. U. Brandes, S. Cornelsen, B. Pampel, and A. Sallaberry. Path-based supports for hypergraphs. J. Discrete Algorithms, 14:248-261, 2012.

    DOI : 10.1016/j.jda.2011.12.009

  5. K. Buchin, M. J. van Kreveld, H. Meijer, B. Speckmann, and K. Verbeek. On planar supports for hyper- graphs. In D. Eppstein and E. R. Gansner, editors, Graph Drawing (GD'09), volume 5849 of LNCS, pages 345-356. Springer, 2009.

    DOI : 10.1007/978-3-642-11805-0

  6. K. Buchin, M. J. van Kreveld, H. Meijer, B. Speckmann, and K. Verbeek. On planar supports for hyper- graphs. J. Graph Algorithms Appl., 15(4):533-549, 2011.

    DOI : 10.7155/jgaa.00237

  7. T. Castermans, M. van Garderen, W. Meulemans, M. Nöllenburg, and X. Yuan. Short plane supports for spatial hypergraphs. In T. Biedl and A. Kerren, editors, Graph Drawing and Network Visualization (GD'18), volume 11282 of LNCS, pages 53-66. Springer International Publishing, 2018.

    DOI : 10.1007/978-3-030-04414-5

  8. T. Castermans, M. van Garderen, W. Meulemans, M. Nöllenburg, and X. Yuan. Short plane supports for spatial hypergraphs. J. Graph Algorithms Appl., 23(3):463-498, 2019.

    DOI : 10.7155/jgaa.00499

  9. H. Chang and H. Lu. Computing the girth of a planar graph in linear time. SIAM J. Comput., 42(3): 1077-1094, 2013.

    DOI : 10.1137/110832033

  10. H. S. M. Coxeter and S. L. Greitzer. Geometry revisited, volume 19. Mathematical Association of America, 1967.

  11. H. de Fraysseix and P. O. de Mendez. Representations by contact and intersection of segments. Algorith- mica, 47(4):453-463, 2007.

    DOI : 10.1007/s00453-006-0157-x

  12. H. de Fraysseix, P. O. de Mendez, and P. Rosenstiehl. Representation of planar hypergraphs by contacts of triangles. In S. Hong, T. Nishizeki, and W. Quan, editors, Proc. Graph Drawing (GD'07), volume 4875 of LNCS, pages 125-136. Springer, 2007.

    DOI : 10.1007/978-3-540-77537-9

  13. D. Eppstein. Testing bipartiteness of geometric intersection graphs. ACM Trans. Algorithms, 5(2):15:1- 15:35, 2009.

    DOI : 10.1145/1497290.1497291

  14. O. Firman and J. Spoerhase. Hypergraph representation via axis-aligned point-subspace cover. Discret. Math. Theor. Comput. Sci., 27(2), 2025.

    DOI : 10.46298/dmtcs.11676

  15. G. Flowers. Embeddings of configurations. PhD thesis, University of Victoria, 2015.

  16. F. Frank, M. Kaufmann, S. G. Kobourov, T. Mchedlidze, S. Pupyrev, T. Ueckerdt, and A. Wolff. Using the metro-map metaphor for drawing hypergraphs. In B. et al., editor, Proc. Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'21), volume 12607 of LNCS, pages 361-372. Springer, 2021.

    DOI : 10.1007/978-3-030-67731-226

  17. D. G. Glynn. On the representation of configurations in projective spaces. Journal of Statistical Planning and Inference, 86(2):443-456, May 2000.

    DOI : 10.1016/s0378-3758(99)00124-x

  18. D. Gonçalves. A planar linear hypergraph whose edges cannot be represented as straight line segments. Eur. J. Comb., 30(1):280-282, 2009.

    DOI : 10.1016/j.ejc.2007.12.004

  19. H. Gropp. Configurations and their realization. Discret. Math., 174(1-3):137-151, 1997.

    DOI : 10.1016/s0012-365x(96)00327-5

  20. B. Grünbaum. Configurations of Points and Lines. American Mathematical Society, 2009. ISBN 9780821843086.

    DOI : 10.1090/gsm/103/02

  21. B. Jacobsen, M. Wallinger, S. G. Kobourov, and M. Nöllenburg. Metrosets: Visualizing sets as metro maps. IEEE Trans. Vis. Comput. Graph., 27(2):1257-1267, 2021.

    DOI : 10.1109/tvcg.2020.3030475

  22. 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

  23. M. Kaufmann and R. Wiese. Embedding vertices at points: Few bends suffice for planar graphs. J. Graph Algorithms Appl., 6(1):115-129, 2002.

    DOI : 10.7155/jgaa.00046

  24. E. J. Kim, A. de Mesmay, and T. Miltzow. Representing matroids over the reals is ∃R-complete. Discret. Math. Theor. Comput. Sci., 26(2), 2024.

    DOI : 10.46298/dmtcs.10810

  25. W. Kocay and R. Szypowski. The application of determining sets to projective configurations. Ars Com- binatoria, 53:193-208, 1999.

    DOI : 10.26493/1855-3974.1059.4be

  26. J. Matousek. Intersection graphs of segments and ∃R. 2014.

    DOI : 10.48550/arXiv.1406.2636

  27. R. M. McConnell and J. P. Spinrad. Modular decomposition and transitive orientation. Discret. Math., 201(1-3):189-241, 1999.

    DOI : 10.1016/s0012-365x(98)00319-7

  28. E. Mäkinen. How to draw a hypergraph. Int. J. Computer Math., 34(3-4):177-185, 1990.

    DOI : 10.1080/00207169008803875

  29. M. Schaefer. Complexity of some geometric and topological problems. In D. Eppstein and E. R. Gansner, editors, Proc. Graph Drawing (GD'09), volume 5849 of LNCS, pages 334-344. Springer, 2009.

    DOI : 10.1007/978-3-642-11805-0

  30. P. W. Shor. Stretchability of pseudolines is NP-hard. In P. Gritzmann and B. 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/AMS, 1990.

    DOI : 10.1090/dimacs/004/41

  31. E. Steinitz. Über die Construction der Configurationen n3 . PhD thesis, Breslau, 1894.

  32. R. Swaminathan and D. K. Wagner. On the consecutive-retrieval problem. SIAM J. Comput., 23 (2):398-414, 1994.

    DOI : 10.1137/s0097539792235487