2-Layer k-Planar Graphs

DOI10.1007/978-3-030-68766-3_32MaRDI QIDQ5014133zbMATH OpenOpenAlexFDO

Authors Patrizio Angelini, Giordano Da Lozzo, Henry Förster, Thomas Schneck

Publication date 1 December 2021

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

Full work available at URL https://doi.org/10.1007/978-3-030-68766-3_32

zbMATH Keywords

densitypathwidthcrossing lemma\(k\)-planar graphsquasiplanar graphs2-layer graph drawing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• 2-layer right angle crossing drawings
• A Turán-type theorem on chords of a convex polygon
• A linear-time algorithm for testing full outer-2-planarity
• A linear-time algorithm for testing outer-1-planarity
• Algorithms and characterizations for 2-layer fan-planarity: from caterpillar to stegosaurus
• Applications of the crossing number
• Beyond outerplanarity
• Beyond-planarity: Turán-type results for non-planar bipartite graphs
• Circular right-angle crossing drawings in linear time
• Coloring k _k -free intersection graphs of geometric objects in the plane
• Crossing Number Problems
• Crossing-Free Subgraphs
• Density of straight-line 1-planar graph drawings
• Discrete and Computational Geometry
• Drawing graphs with right angle crossings
• Ein Sechsfarbenproblem auf der Kugel
• Fan-planarity: properties and complexity
• Graph Drawing and Applications for Software and Knowledge Engineers
• Graphs drawn with few crossings per edge
• Improving the crossing lemma by finding more crossings in sparse graphs
• On Layered Fan-Planar Graph Drawings
• On Optimal 2- and 3-Planar Graphs
• On RAC drawings of graphs with one bend per edge
• On geometric graphs with no \(k\) pairwise parallel edges
• On the density of non-simple 3-planar graphs
• On the maximum number of edges in quasi-planar graphs
• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• On the parameterized complexity of layered graph drawing
• On the recognition of fan-planar and maximal outer-fan-planar graphs
• On topological graphs with at most four crossings per edge
• Outer 1-planar graphs
• Proofs from THE BOOK. Including illustrations by Karl H. Hofmann
• Quasi-planar graphs have a linear number of edges
• Right angle crossing graphs and 1-planarity
• Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar
• The crossing-angle resolution in graph drawing
• The number of edges in \(k\)-quasi-planar graphs

Cited in

(1)

• 2-Layer Graph Drawings with Bounded Pathwidth

This page was built for publication: 2-Layer k-Planar Graphs

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