Top

Published in:

2020 | OriginalPaper | Chapter

An Experimental Study of a 1-Planarity Testing and Embedding Algorithm

Authors : Carla Binucci, Walter Didimo, Fabrizio Montecchiani

Published in: WALCOM: Algorithms and Computation

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

A graph is 1-planar if it can be drawn in the plane with at most one crossing per edge. The 1-planarity testing problem is NP-complete, even for restricted classes of graphs. We present the first general 1-planarity testing and embedding algorithm, and we experimentally investigate its feasibility in practice. The results suggest that our approach can be successfully applied to graphs with up to 30 vertices, while more sophisticated techniques are needed to attack larger graphs.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Parameterized Algorithms for the Happy Set Problem

next chapter Trichotomy for the Reconfiguration Problem of Integer Linear Systems

http://www.graphdrawing.org/data.html. Accessed June 2019

Auer, C., et al.: Outer 1-planar graphs. Algorithmica 74(4), 1293–1320 (2016)MathSciNetMATHCrossRef

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

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

Binucci, C., Didimo, W., Montecchiani, F.: An experimental study of a 1-planarity testing and embedding algorithm. CoRR arXiv:1911.00573 (2019)

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

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

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

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

10.

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

11.

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Upper Saddle River (1999)MATH

12.

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

13.

Di Giacomo, E., et al.: Ortho-polygon visibility representations of embedded graphs. Algorithmica 80(8), 2345–2383 (2018)MathSciNetMATHCrossRef

14.

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

15.

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

16.

Gutwenger, C., Mutzel, P.: An experimental study of crossing minimization heuristics. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 13–24. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24595-7_2MATHCrossRef

17.

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

18.

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

19.

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

20.

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

Title: An Experimental Study of a 1-Planarity Testing and Embedding Algorithm
Authors: Carla Binucci
Walter Didimo
Fabrizio Montecchiani
Publisher: Springer International Publishing
Book: WALCOM: Algorithms and Computation
Print ISBN: 978-3-030-39880-4

Electronic ISBN: 978-3-030-39881-1

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-39881-1_28

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner