2-Layer k-Planar Graphs

DOI10.1007/978-3-030-68766-3_32OpenAlexW3133920734MaRDI QIDQ5014133FDOQ5014133

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

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

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)