Ordered Level Planarity, Geodesic Planarity and Bi-Monotonicity

DOI10.1007/978-3-319-73915-1_34zbMath1503.68226arXiv1708.07428OpenAlexW3105529179WikidataQ127155522 ScholiaQ127155522MaRDI QIDQ4625134

Boris Klemz, Günter Rote

Publication date: 20 February 2019

Published in: Lecture Notes in Computer Science, ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1708.07428

zbMATH Keywords

graph drawingNP-hardnesslevel planarityupward drawingsorthogeodesic drawingspoint-set embedability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Drawing two posets, Ordered Level Planarity, Geodesic Planarity and Bi-Monotonicity, Non-crossing Paths with Geographic Constraints, Level planarity: transitivity vs. even crossings, Extending upward planar graph drawings, Beyond level planarity: cyclic, torus, and simultaneous level planarity, Computing k-modal embeddings of planar digraphs, Multilevel Planarity, Level-planarity: transitivity vs. even crossings

Cites Work

• Generalized \(k\)-ary tanglegrams on level graphs: a satisfiability-based approach and its evaluation
• Hamiltonian orthogeodesic alternating paths
• Orthogeodesic point-set embedding of trees
• On the Computational Complexity of Upward and Rectilinear Planarity Testing
• Hanani–Tutte, Monotone Drawings, and Level-Planarity
• The Importance of Being Proper
• Beyond Level Planarity
• Radial Level Planarity Testing and Embedding in Linear Time
• Linear Time Planarity Testing and Embedding of Strongly Connected Cyclic Level Graphs
• Manhattan-Geodesic Embedding of Planar Graphs
• Hierarchies and planarity theory
• Partial and Constrained Level Planarity
• Ordered Level Planarity, Geodesic Planarity and Bi-Monotonicity
• OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
• SOFSEM 2004: Theory and Practice of Computer Science