On the Pagenumber of 1-Planar Graphs

Abstract

A book embedding of a graph G is a placement of its vertices along the spine of a book, and an assignment of its edges to the pages such that no two edges on the same page cross. The pagenumber of a graph is the minimum number of pages in which it can be embedded. Determining the pagenumber of a graph is NP-hard. A graph is said to be 1-planar if it can be drawn in the plane so that each edge is crossed at most once. The anthors prove that the pagenumber of 1-planar graphs is at most 10.

Keywords

Book embedding / 1-Planar graph / Pagenumber / Crossing

References

[1] AlamM J, BrandenburgF J, KobourovS G. Straight-line grid drawings of 3-connected 1-planar graphs. Graph Drawing (GD13), 2013, Cham, Springer-Verlag: 83-948242

[2] Alam, M. J., Brandenburg, F. J. and Kobourov, S. G., On the book thickness of 1-planar graphs, Computer Science Computational Geometry, arXiv:1510.05891, 2015.

[3] BekosM A, BruckdorferT, KaufmannM, RaftopoulouC N. 1-Planar graphs have constant book thickness. Algorithmica, 2017, 79: 444-465

[4] BekosM A, KaufmannM, ZielkeC. The book embedding problem from a SAT solver perspective. Graph drawing and network visualization, 2015, Cham, Springer-Varly: 125-1389411

[5] BernhartF, KainenP C. The book thickness of a graph. J. Comb. Theory B, 1979, 27(3): 320-331

[6] BilskiT. Optimum embedding of complete graphs in books. Discrete Math., 1998, 182: 21-28

[7] BrandenburgF J. 1-Visibility representations of 1-planar graphs. J. Graph Algorithms and Applications, 2014, 18(3): 421-438

[8] BrandenburgF J. Characterizing and recognizing 4-map graphs. Algorithmica, 2019, 81(5): 1818-1843

[9] BussJ F, ShorP W. On the pagenumber of planar graphs. Proceedings of the 16th ACM Symposium on Theory of Computing (STOC84), 198498-100

[10] ChungF R K, LeightonF T, RosenbergA L. Embedding graphs in books: A layout problem with applications to VLSI design. SIAM J. Algebraic Discrete Methods, 1987, 8: 33-58

[11] DujmovicV, WoodD R. Graph treewidth and geometric thickness parameters. Discrete & Comput. Geom., 2007, 37: 641-670

[12] EnomotoH, NakamigawaT, OtaK. On the pagenumber of complete bipartite graphs. J. Comb. Theory B, 1997, 71: 111-120

[13] EvenS, ItaiA. Queues, stacks, and graphs. Theory of Machines and Computations, 1971, New York-London, Academic Press: 71-86

[14] FabriciI, MadarasT. The structure of 1-planar graphs. Discrete Math., 2007, 307: 854-865

[15] GrigorievA, BodlaenderH L. Algorithms for graphs embeddable with few crossings per edge. Algorithmica, 2007, 49(1): 1-11

[16] HeathL. Embedding planar graphs in seven pages. Proceedings of the 25th IEEE Annual Symposium on Foundations of Computer Science, 198474-89

[17] IstrailS. An algorithm for embedding planar graphs in six pages. An Stiint. Uniov. Al. I. Guza Iasi Sect. I a Mat., 1988, 34(4): 329-341

[18] KapoorN, RussellM, StojmenovicI, ZomayaA Y. A genetic algorithm for finding the pagenumber of interconnection networks. J. Parallel Distrib. Comput., 2002, 62: 267-283

[19] KobourovS G. Liotta, G. and Montecchiani, F, An annotated bibliography on 1-planarity. Comput. Sci. Rew., 2017, 25: 49-67

[20] KorzhikV P, MoharB. Minimal obstructions for 1-immersions and hardness of 1-planarity testing. J. Graph Theory, 2013, 72: 30-71

[21] MuderD J, WeaverM L, WestD B. Pagenumber of complete bipartite graphs. J. Graph Theory, 1988, 12: 469-489

[22] NowakowskiR, ParkerA. Ordered sets, pagenumbers, and planarity. Order, 1989, 6: 209-218

[23] PachJ, TóthG. Graphs drawn with a few crossings per edge. Combinatorica, 1997, 17: 427-439

[24] RosenbergA L. The Diogenes approach to testable fault-tolerant arrays of processors. IEEE T. Comput., 1983, 32: 902-910

[25] SoH C. Some theoretical results on the routing of multilayer printed-wiring boards. IEEE International Symposium On Circuits and Systems, 1974296-303

[26] TamassiaRHandbook of Graph Drawing and Visualization, 2013, New York, CRC Press

[27] ThomassenC. Rectilinear drawings of graphs. J. Graph Theory, 1988, 12: 335-341

[28] WigdersonAThe complexity of the Hamiltonian circuit problem for maximal planar graphs, 1982February298

[29] YannakakisM. Four pages are necessary and sufficient for planar graphs. ACM Symposium on Theory of Computing (STOC86), 1986104-108(extended abstract)

[30] YannakakisM. Embedding planar graphs in four pages. J. Comput. System Sci., 1989, 38: 36-67

[31] YannakakisM. Planar graphs that need four pages. J. Comb. Theory Ser. B, 2020, 145: 241-263

RIGHTS & PERMISSIONS

The Editorial Office of CAM and Springer-Verlag Berlin Heidelberg