Inserting multiple edges into a planar graph

DOI10.4230/LIPICS.SOCG.2016.30zbMATH Open1388.68216arXiv1509.07952MaRDI QIDQ3132864FDOQ3132864

Authors: Markus Chimani, Petr Hliněný 

Publication date: 30 January 2018

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

Recommendations

• A tighter insertion-based approximation of the crossing number
• A tighter insertion-based approximation of the crossing number
• Inserting an edge into a planar graph
• Inserting an edge into a planar graph
• Inserting an edge into a geometric embedding

zbMATH Keywords

parameterized complexitycrossing numberpath homotopyedge insertionfunnel algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited In (15)

• Crossing number for graphs with bounded pathwidth
• Crossing numbers and stress of random graphs
• A tighter insertion-based approximation of the crossing number
• Planarizing graphs and their drawings by vertex splitting
• A Note on the Practicality of Maximal Planar Subgraph Algorithms
• Title not available (Why is that?)
• Inserting an edge into a geometric embedding
• Inserting one edge into a simple drawing is hard
• Inserting Multiple Edges into a Planar Graph
• Parameterized analysis and crossing minimization problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Extension of some edge graph problems: standard, parameterized and approximation complexity
• Inserting an edge into a geometric embedding
• 1-planarity testing and embedding: an experimental study

This page was built for publication: Inserting multiple edges into a planar graph

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