License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.19
URN: urn:nbn:de:0030-drops-94829
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9482/
Go to the corresponding LIPIcs Volume Portal

Chimani, Markus ; Wiedera, Tilo

Cycles to the Rescue! Novel Constraints to Compute Maximum Planar Subgraphs Fast

pdf-format:
LIPIcs-ESA-2018-19.pdf (0.5 MB)

Abstract

The NP-hard Maximum Planar Subgraph problem asks for a planar subgraph H of a given graph G such that H has maximum edge cardinality. For more than two decades, the only known non-trivial exact algorithm was based on integer linear programming and Kuratowski's famous planarity criterion. We build upon this approach and present new constraint classes - together with a lifting of the polyhedron - to obtain provably stronger LP-relaxations, and in turn faster algorithms in practice. The new constraints take Euler's polyhedron formula as a starting point and combine it with considering cycles in G. This paper discusses both the theoretical as well as the practical sides of this strengthening.

BibTeX - Entry

@InProceedings{chimani_et_al:LIPIcs:2018:9482,
  author =	{Markus Chimani and Tilo Wiedera},
  title =	{{Cycles to the Rescue! Novel Constraints to Compute Maximum Planar Subgraphs Fast}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Yossi Azar and Hannah Bast and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9482},
  URN =		{urn:nbn:de:0030-drops-94829},
  doi =		{10.4230/LIPIcs.ESA.2018.19},
  annote =	{Keywords: algorithm engineering, graph algorithms, integer linear programming, maximum planar subgraph}
}

Keywords: algorithm engineering, graph algorithms, integer linear programming, maximum planar subgraph
Collection: 26th Annual European Symposium on Algorithms (ESA 2018)
Issue Date: 2018
Date of publication: 14.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI