Beyond level planarity

DOI10.1007/978-3-319-50106-2_37MaRDI QIDQ2961540zbMATH OpenOpenAlexFDO

Authors Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Ignaz Rutter

Publication date 21 February 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

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)

Abstract: In this paper we settle the computational complexity of two open problems related to the extension of the notion of level planarity to surfaces different from the plane. Namely, we show that the problems of testing the existence of a level embedding of a level graph on the surface of the rolling cylinder or on the surface of the torus, respectively known by the name of $extitCyclicLevelPlanarity$ and $extitTorusLevelPlanarity$, are polynomial-time solvable. Moreover, we show a complexity dichotomy for testing the $extitSimultaneousLevelPlanarity$ of a set of level graphs, with respect to both the number of level graphs and the number of levels.

Recommendations

• Beyond level planarity: cyclic, torus, and simultaneous level planarity
• Cyclic Level Planarity Testing and Embedding
• Radial level planarity with fixed embedding
• Linear Time Planarity Testing and Embedding of Strongly Connected Cyclic Level Graphs
• Level Planar Embedding in Linear Time

Cites work

• A characterization of level planar graphs
• A new perspective on clustered planarity as a combinatorial embedding problem
• A satisfiability formulation of problems on level graphs
• Beyond level planarity
• Classification of planar upward embedding
• Cyclic Level Planarity Testing and Embedding
• Generalized \(k\)-ary tanglegrams on level graphs: a satisfiability-based approach and its evaluation
• Hanani-Tutte, monotone drawings, and level-planarity
• Hierarchies and planarity theory
• Linear Time Planarity Testing and Embedding of Strongly Connected Cyclic Level Graphs
• On simultaneous planar graph embeddings
• On the characterization of level planar trees by minimal patterns
• Radial Level Planarity Testing and Embedding in Linear Time
• SOFSEM 2004: Theory and Practice of Computer Science
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Testing simultaneous planarity when the common graph is 2-connected
• The importance of being proper
• Total Ordering Problem
• Upward planar drawings on the standing and the rolling cylinders

Cited in

(11)

• Cyclic Level Planarity Testing and Embedding
• Computing k-modal embeddings of planar digraphs
• Perfect level sets in many directions
• Lower levels of Euclidean planes
• Level-planar drawings with few slopes
• Simultaneous orthogonal planarity
• Beyond level planarity
• Beyond level planarity: cyclic, torus, and simultaneous level planarity
• Partial and Constrained Level Planarity
• Simultaneous Embedding
• Hanani-Tutte for approximating maps of graphs

This page was built for publication: Beyond level planarity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2961540)