Level-planarity: transitivity vs. even crossings
type: Item
instance of: scholarly article
title: Level-planarity: transitivity vs. even crossings
zbMATH Open document ID: 1503.05025
DOI: 10.37236/10814
author: Guido Brückner
author: Ignaz Rutter
author: Peter Stumpf
published in: The Electronic Journal of Combinatorics
publication date: 2022-11-08T00:00:00Z
review text: Summary: \textit{R. Fulek} et al. [in: Thirty essays on geometric graph theory. Berlin: Springer. 263--287 (2013; Zbl 1272.05129); Lect. Notes Comput. Sci. 9801, 468--481 (2016; Zbl 1478.68237)] have presented Hanani-Tutte results for (radial) level-planarity, i.e., a graph is (radial) level-planar if it admits a (radial) level drawing where any two independent edges cross an even number of times. We show that the 2-SAT formulation of level-planarity testing due to \textit{B. Randerath} et al. [Electron. Notes Discrete Math. 9, no pag. (2001; Zbl 0990.90530)] is equivalent to the strong Hanani-Tutte theorem for level-planarity. By elevating this relationship to radial level-planarity, we obtain a novel polynomial-time algorithm for testing radial level-planarity in the spirit of Randerath et al..
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 7613677
zbMATH Keywords: orientable surface
zbMATH Keywords: independent edge crossing
zbMATH Keywords: graph drawing
zbMATH Keywords: Hanani-Tutte theorem
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.37236/10814
OpenAlex ID: W2952121550
cites work: Beyond level planarity: cyclic, torus, and simultaneous level planarity
cites work: Radial Level Planarity Testing and Embedding in Linear Time
cites work: Linear Time Planarity Testing and Embedding of Strongly Connected Cyclic Level Graphs
cites work: Cyclic Level Planarity Testing and Embedding
cites work: Computing and Combinatorics
cites work: Partial and Constrained Level Planarity
cites work: Über wesentlich unplättbare Kurven im dreidimensionalen Raume
cites work: A Direct Proof of the Strong Hanani-Tutte Theorem on the Projective Plane
cites work: Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4
cites work: Hanani-Tutte for Radial Planarity II
cites work: Hanani-Tutte for Radial Planarity
cites work: Hanani–Tutte, Monotone Drawings, and Level-Planarity
cites work: On the computational complexity of upward and rectilinear planarity testing
cites work: Practical Level Planarity Testing and Layout with Embedding Constraints
cites work: Level Planar Embedding in Linear Time
cites work: Ordered Level Planarity, Geodesic Planarity and Bi-Monotonicity
cites work: The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
cites work: Towards an implementation of the 3D visibility skeleton
cites work: Strong Hanani–Tutte on the Projective Plane
cites work: Removing even crossings on surfaces
cites work: Toward a theory of crossing numbers
description: scientific article; zbMATH DE number 7613677