research-article

1-planarity testing and embedding: : An experimental study

Authors:

Fabrizio MontecchianiAuthors Info & Claims

Volume 108, Issue C

https://doi.org/10.1016/j.comgeo.2022.101900

Published: 01 January 2023 Publication History

Abstract

Many papers study the natural problem of drawing nonplanar graphs with few crossings per edge. In particular, a graph is 1-planar if it can be drawn in the plane with at most one crossing per edge. Unfortunately, while testing graph planarity is solvable in linear time and several efficient algorithms have been described in the literature, deciding whether a graph is 1-planar is NP-complete, even for restricted classes of graphs. Despite some polynomial-time algorithms are known for recognizing specific subfamilies of 1-planar graphs, there is still a lack of practical 1-planarity testing algorithms and no implementation is available for general graphs. This paper investigates the feasibility of a 1-planarity testing and embedding algorithm based on a backtracking strategy. Our contribution provides initial indications that have the potential to stimulate further research on the design of practical approaches for the 1-planarity testing problem. On the one hand, our experiments show that a backtracking strategy can be successfully applied to graphs with up to 30 vertices. On the other hand, our study suggests that alternative techniques are needed to attack larger graphs.

References

[1]

C. Binucci, W. Didimo, F. Montecchiani, An experimental study of a 1-planarity testing and embedding algorithm, in: WALCOM, in: LNCS, vol. 12049, Springer, 2020, pp. 329–335.

[2]

D. Eppstein, Diameter and treewidth in minor-closed graph families, Algorithmica 27 (3) (2000) 275–291.

[3]

D. Eppstein, S. Gupta, Crossing patterns in nonplanar road networks, in: SIGSPATIAL/GIS, ACM, 2017.

[4]

D. Eppstein, M. Löffler, D. Strash, Listing all maximal cliques in large sparse real-world graphs, ACM J. Exp. Algorithmics 18 (2013).

[5]

A. Grigoriev, H.L. Bodlaender, Algorithms for graphs embeddable with few crossings per edge, Algorithmica 49 (1) (2007) 1–11.

Digital Library

[6]

M. Grohe, Local tree-width, excluded minors, and approximation algorithms, Combinatorica 23 (4) (2003) 613–632.

Digital Library

[7]

W. Didimo, P. Eades, G. Liotta, Drawing graphs with right angle crossings, Theor. Comput. Sci. 412 (39) (2011) 5156–5166.

[8]

W. Huang, P. Eades, S. Hong, Larger crossing angles make graphs easier to read, J. Vis. Lang. Comput. 25 (4) (2014) 452–465.

Digital Library

[9]

M.A. Bekos, M. Kaufmann, F. Montecchiani, Guest editors' foreword and overview, Special Issue on Graph Drawing Beyond Planarity, J. Graph Algorithms Appl. 22 (1) (2018) 1–10.

[10]

W. Didimo, G. Liotta, F. Montecchiani, A survey on graph drawing beyond planarity, ACM Comput. Surv. 52 (1) (2019).

[11]

S. Hong, M. Kaufmann, S.G. Kobourov, J. Pach, Beyond-planar graphs: algorithmics and combinatorics, Dagstuhl Seminar 16452, Dagstuhl Rep. 6 (11) (2016) 35–62.

[12]

S. Hong, T. Tokuyama (Eds.), Beyond Planar Graphs, Communications of NII Shonan Meetings, Springer, 2020.

[13]

S.G. Kobourov, G. Liotta, F. Montecchiani, An annotated bibliography on 1-planarity, Comput. Sci. Rev. 25 (2017) 49–67.

[14]

S. Hong, Algorithms for 1-planar graphs, in: Beyond Planar Graphs, Springer, 2020, pp. 69–87.

[15]

J. Pach, G. Tóth, Graphs drawn with few crossings per edge, Combinatorica 17 (3) (1997) 427–439.

[16]

Alam, M.J.; Brandenburg, F.J.; Kobourov, S.G. (2015): On the book thickness of 1-planar graphs. CoRR arXiv:1510.05891.

[17]

M.A. Bekos, T. Bruckdorfer, M. Kaufmann, C.N. Raftopoulou, The book thickness of 1-planar graphs is constant, Algorithmica 79 (2) (2017) 444–465.

Digital Library

[18]

V. Dujmovic, G. Joret, P. Micek, P. Morin, T. Ueckerdt, D.R. Wood, Planar graphs have bounded queue-number, J. ACM 67 (4) (2020).

Digital Library

[19]

V.P. Korzhik, B. Mohar, Minimal obstructions for 1-immersions and hardness of 1-planarity testing, J. Graph Theory 72 (1) (2013) 30–71.

Digital Library

[20]

M.J. Bannister, S. Cabello, D. Eppstein, Parameterized complexity of 1-planarity, J. Graph Algorithms Appl. 22 (1) (2018) 23–49.

[21]

S. Cabello, B. Mohar, Adding one edge to planar graphs makes crossing number and 1-planarity hard, SIAM J. Comput. 42 (5) (2013) 1803–1829.

Digital Library

[22]

C. Auer, F.J. Brandenburg, A. Gleißner, J. Reislhuber, 1-planarity of graphs with a rotation system, J. Graph Algorithms Appl. 19 (1) (2015) 67–86.

[23]

F.J. Brandenburg, Recognizing optimal 1-planar graphs in linear time, Algorithmica 80 (1) (2018) 1–28.

[24]

P. Eades, S. Hong, N. Katoh, G. Liotta, P. Schweitzer, Y. Suzuki, A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system, Theor. Comput. Sci. 513 (2013) 65–76.

[25]

C. Auer, C. Bachmaier, F.J. Brandenburg, A. Gleißner, K. Hanauer, D. Neuwirth, J. Reislhuber, Outer 1-planar graphs, Algorithmica 74 (4) (2016) 1293–1320.

[26]

S. Hong, P. Eades, N. Katoh, G. Liotta, P. Schweitzer, Y. Suzuki, A linear-time algorithm for testing outer-1-planarity, Algorithmica 72 (4) (2015) 1033–1054.

[27]

F.J. Brandenburg, Characterizing and recognizing 4-map graphs, Algorithmica 81 (5) (2019) 1818–1843.

Digital Library

[28]

M.J. Alam, F.J. Brandenburg, S.G. Kobourov, Straight-line grid drawings of 3-connected 1-planar graphs, in: Graph Drawing, in: LNCS, vol. 8242, Springer, 2013, pp. 83–94.

[29]

M.A. Bekos, W. Didimo, G. Liotta, S. Mehrabi, F. Montecchiani, On RAC drawings of 1-planar graphs, Theor. Comput. Sci. 689 (2017) 48–57.

[30]

T.C. Biedl, G. Liotta, F. Montecchiani, Embedding-preserving rectangle visibility representations of nonplanar graphs, Discrete Comput. Geom. 60 (2) (2018) 345–380.

[31]

E. Di Giacomo, W. Didimo, W.S. Evans, G. Liotta, H. Meijer, F. Montecchiani, S.K. Wismath, Ortho-polygon visibility representations of embedded graphs, Algorithmica 80 (8) (2018) 2345–2383.

[32]

S. Hong, P. Eades, G. Liotta, S. Poon, Fáry's theorem for 1-planar graphs, in: COCOON, in: LNCS, vol. 7434, Springer, 2012, pp. 335–346.

[33]

S. Hong, H. Nagamochi, Re-embedding a 1-plane graph into a straight-line drawing in linear time, in: Graph Drawing, in: LNCS, vol. 9801, Springer, 2016, pp. 321–334.

[34]

G. Liotta, F. Montecchiani, A. Tappini, Ortho-polygon visibility representations of 3-connected 1-plane graphs, Theor. Comput. Sci. 863 (2021) 40–52.

[35]

: http://www.graphdrawing.org/data.html (online).

[36]

G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, F. Vargiu, An experimental comparison of four graph drawing algorithms, Comput. Geom. 7 (1997) 303–325.

[37]

M. Chimani, P. Kindermann, F. Montecchiani, P. Valtr, Crossing numbers of beyond-planar graphs, Theor. Comput. Sci. 898 (2022) 44–49.

[38]

C. Gutwenger, P. Mutzel, An experimental study of crossing minimization heuristics, in: G. Liotta (Ed.), GD 2003, in: LNCS, vol. 2912, Springer, 2003, pp. 13–24.

[39]

: http://mozart.diei.unipg.it/montecchiani/1planarity/labels.xlsx (online).

[40]

F.J. Brandenburg, 1-visibility representations of 1-planar graphs, J. Graph Algorithms Appl. 18 (3) (2014) 421–438.

[41]

M. Chimani, P. Hlinený, Inserting multiple edges into a planar graph, in: SoCG 2016, in: LIPIcs, vol. 51, Schloss Dagstuhl, 2016.

[42]

M. Chimani, C. Gutwenger, M. Jünger, G.W. Klau, K. Klein, P. Mutzel, The open graph drawing framework (OGDF), in: Handbook of Graph Drawing and Visualization, Chapman and Hall/CRC, 2013, pp. 543–569.

[43]

C. Gutwenger, P. Mutzel, R. Weiskircher, Inserting an edge into a planar graph, Algorithmica 41 (4) (2005) 289–308.

[44]

M. Chimani, C. Gutwenger, Advances in the planarization method: effective multiple edge insertions, J. Graph Algorithms Appl. 16 (3) (2012) 729–757.

[45]

R. Jayakumar, K. Thulasiraman, M.N.S. Swamy, O( n 2 ) algorithms for graph planarization, IEEE Trans. CAD Integr. Circuits Syst. 8 (3) (1989) 257–267.

[46]

M. Chimani, P. Mutzel, I.M. Bomze, A new approach to exact crossing minimization, in: ESA, in: LNCS, vol. 5193, Springer, 2008, pp. 284–296.

[47]

M.A. Bekos, S. Cornelsen, L. Grilli, S. Hong, M. Kaufmann, On the recognition of fan-planar and maximal outer-fan-planar graphs, Algorithmica 79 (2) (2017) 401–427.

[48]

C. Binucci, E. Di Giacomo, W. Didimo, F. Montecchiani, M. Patrignani, A. Symvonis, I.G. Tollis, Fan-planarity: properties and complexity, Theor. Comput. Sci. 589 (2015) 76–86.

Index Terms

1-planarity testing and embedding: An experimental study
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Design and analysis of algorithms
  2. Randomness, geometry and discrete structures

Index terms have been assigned to the content through auto-classification.

Recommendations

A Linear-Time Algorithm for Testing Outer-1-Planarity

A graph is 1-planar if it can be embedded in the plane with at most one crossing per edge. It is known that the problem of testing 1-planarity of a graph is NP-complete. In this paper, we study outer-1-planar graphs. A graph is outer-1-planar if it has ...
A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system

A 1-planar graph is a graph that can be embedded in the plane with at most one crossing per edge. It is known that testing 1-planarity of a graph is NP-complete. In this paper, we consider maximal 1-planar graphs. A graph G is maximal 1-planar if ...
Some sufficient conditions for 1-planar graphs to be Class 1

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. Let G be a 1-planar graph with maximum degree Δ ( G ) . In this paper, it is shown that ' ( G ) = Δ ( G ) if (1) Δ ( G ) 9 and G contains no ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computational Geometry: Theory and Applications

Computational Geometry: Theory and Applications Volume 108, Issue C

Jan 2023

156 pages

ISSN:0925-7721

Issue’s Table of Contents

Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 January 2023

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents