Algorithms for graphs embeddable with few crossings per edge

DOI10.1007/s00453-007-0010-xzbMath1131.68120OpenAlexW2899777575WikidataQ30053231 ScholiaQ30053231MaRDI QIDQ2461632

Alexander Grigoriev, Hans L. Bodlaender

Publication date: 28 November 2007

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://dspace.library.uu.nl/handle/1874/17980

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (55)

The density of fan-planar graphs ⋮ Recognizing and drawing IC-planar graphs ⋮ A survey on book-embedding of planar graphs ⋮ Fixed-parameter tractability for book drawing with bounded number of crossings per edge ⋮ On fan-crossing and fan-crossing free graphs ⋮ Recognizing IC-Planar and NIC-Planar Graphs ⋮ Linear-time recognition of map graphs with outerplanar witness ⋮ On RAC drawings of 1-planar graphs ⋮ Parameterized analysis and crossing minimization problems ⋮ Fan-crossing free graphs and their relationship to other beyond-planar graphs ⋮ An annotated bibliography on 1-planarity ⋮ A fast algorithm for the product structure of planar graphs ⋮ On the recognition of fan-planar and maximal outer-fan-planar graphs ⋮ The book thickness of 1-planar graphs is constant ⋮ \(\mathsf{NIC}\)-planar graphs ⋮ Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets ⋮ A Note on the Minimum H-Subgraph Edge Deletion ⋮ Structure of Graphs with Locally Restricted Crossings ⋮ PTAS for Sparse General-valued CSPs ⋮ All 2-planar graphs having the same spanning subgraph ⋮ The family of fan-planar graphs ⋮ Weak-dynamic coloring of graphs beyond-planarity ⋮ Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time ⋮ On the Density of Non-simple 3-Planar Graphs ⋮ On the edge crossing properties of Euclidean minimum weight Laman graphs ⋮ Treewidth, Circle Graphs, and Circular Drawings ⋮ Recognizing optimal 1-planar graphs in linear time ⋮ \(\mathsf{T}\)-shape visibility representations of 1-planar graphs ⋮ 1-fan-bundle-planar drawings of graphs ⋮ 3D Visibility Representations of 1-planar Graphs ⋮ Gap-Planar Graphs ⋮ A linear-time algorithm for testing full outer-2-planarity ⋮ Complexity of Geometric k-Planarity for Fixed k ⋮ A linear-time algorithm for testing outer-1-planarity ⋮ Re-embedding a 1-plane graph for a straight-line drawing in linear time ⋮ Characterizing and recognizing 4-map graphs ⋮ On partitioning the edges of 1-plane graphs ⋮ Characterizing 5-map graphs by 2-fan-crossing graphs ⋮ Unnamed Item ⋮ Gap-planar graphs ⋮ Testing gap \(k\)-planarity is NP-complete ⋮ Planar graphs having no proper 2-immersions in the plane. I ⋮ Testing Full Outer-2-planarity in Linear Time ⋮ On 3D visibility representations of graphs with few crossings per edge ⋮ Beyond Planar Graphs: Introduction ⋮ Quantitative Restrictions on Crossing Patterns ⋮ 1-Planar Graphs ⋮ Algorithms for 1-Planar Graphs ⋮ Edge Partitions and Visibility Representations of 1-planar Graphs ⋮ $$\textit{\textbf{k}}$$-Planar Graphs ⋮ Fan-Planar Graphs ⋮ 1-planarity testing and embedding: an experimental study ⋮ Fan-planarity: properties and complexity ⋮ On the Number of Edges of Fan-Crossing Free Graphs ⋮ Counting cliques in 1-planar graphs

This page was built for publication: Algorithms for graphs embeddable with few crossings per edge