Beyond level planarity

DOI10.1007/978-3-319-50106-2_37zbMATH Open1436.68376arXiv1510.08274OpenAlexW2963969949MaRDI QIDQ2961540FDOQ2961540

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)

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.

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

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

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)

Cites Work

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

Cited In (11)

• Cyclic Level Planarity Testing and Embedding
• Computing k-modal embeddings of planar digraphs
• Perfect level sets in many directions
• Level-planar drawings with few slopes
• Lower levels of Euclidean planes
• 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)