A note on the practicality of maximal planar subgraph algorithms
| dc.contributor.author | Chimani, Markus | |
| dc.contributor.author | Klein, Karsten | |
| dc.contributor.author | Wiedera, Tilo | |
| dc.date.accessioned | 2017-01-20T10:00:47Z | |
| dc.date.available | 2017-01-20T10:00:47Z | |
| dc.date.issued | 2016 | eng |
| dc.description.abstract | Given a graph G, the NP-hard Maximum Planar Subgraph problem (MPS) asks for a planar subgraph of G with the maximum number of edges. There are several heuristic, approximative, and exact algorithms to tackle the problem, but—to the best of our knowledge—they have never been compared competitively in practice. We report on an exploratory study on the relative merits of the diverse approaches, focusing on practical runtime, solution quality, and implementation complexity. Surprisingly, a seemingly only theoretically strong approximation forms the building block of the strongest choice. | eng |
| dc.description.version | published | eng |
| dc.identifier.doi | 10.1007/978-3-319-50106-2_28 | eng |
| dc.identifier.uri | https://kops.uni-konstanz.de/handle/123456789/36860 | |
| dc.language.iso | eng | eng |
| dc.subject.ddc | 004 | eng |
| dc.title | A note on the practicality of maximal planar subgraph algorithms | eng |
| dc.type | INPROCEEDINGS | eng |
| dspace.entity.type | Publication | |
| kops.citation.bibtex | @inproceedings{Chimani2016pract-36860,
year={2016},
doi={10.1007/978-3-319-50106-2_28},
title={A note on the practicality of maximal planar subgraph algorithms},
number={9801},
isbn={978-3-319-50105-5},
publisher={Springer International Publishing - Springer},
address={Cham},
series={Lecture Notes in Computer Science},
booktitle={Graph Drawing and Network Visualization : 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers},
pages={357--364},
editor={Hu, Yifan and Nöllenburg, Martin},
author={Chimani, Markus and Klein, Karsten and Wiedera, Tilo}
} | |
| kops.citation.iso690 | CHIMANI, Markus, Karsten KLEIN, Tilo WIEDERA, 2016. A note on the practicality of maximal planar subgraph algorithms. International Symposium on Graph Drawing and Network Visualization. Athens, Greece, 19. Sept. 2016 - 21. Sept. 2016. In: HU, Yifan, ed., Martin NÖLLENBURG, ed.. Graph Drawing and Network Visualization : 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers. Cham: Springer International Publishing - Springer, 2016, pp. 357-364. Lecture Notes in Computer Science. 9801. ISBN 978-3-319-50105-5. Available under: doi: 10.1007/978-3-319-50106-2_28 | deu |
| kops.citation.iso690 | CHIMANI, Markus, Karsten KLEIN, Tilo WIEDERA, 2016. A note on the practicality of maximal planar subgraph algorithms. International Symposium on Graph Drawing and Network Visualization. Athens, Greece, Sep 19, 2016 - Sep 21, 2016. In: HU, Yifan, ed., Martin NÖLLENBURG, ed.. Graph Drawing and Network Visualization : 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers. Cham: Springer International Publishing - Springer, 2016, pp. 357-364. Lecture Notes in Computer Science. 9801. ISBN 978-3-319-50105-5. Available under: doi: 10.1007/978-3-319-50106-2_28 | eng |
| kops.citation.rdf | <rdf:RDF
xmlns:dcterms="http://purl.org/dc/terms/"
xmlns:dc="http://purl.org/dc/elements/1.1/"
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:bibo="http://purl.org/ontology/bibo/"
xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
xmlns:foaf="http://xmlns.com/foaf/0.1/"
xmlns:void="http://rdfs.org/ns/void#"
xmlns:xsd="http://www.w3.org/2001/XMLSchema#" >
<rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36860">
<dc:creator>Chimani, Markus</dc:creator>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/36860"/>
<dc:creator>Wiedera, Tilo</dc:creator>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dcterms:abstract xml:lang="eng">Given a graph G, the NP-hard Maximum Planar Subgraph problem (MPS) asks for a planar subgraph of G with the maximum number of edges. There are several heuristic, approximative, and exact algorithms to tackle the problem, but—to the best of our knowledge—they have never been compared competitively in practice. We report on an exploratory study on the relative merits of the diverse approaches, focusing on practical runtime, solution quality, and implementation complexity. Surprisingly, a seemingly only theoretically strong approximation forms the building block of the strongest choice.</dcterms:abstract>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2017-01-20T10:00:47Z</dc:date>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dc:contributor>Wiedera, Tilo</dc:contributor>
<dcterms:issued>2016</dcterms:issued>
<dc:creator>Klein, Karsten</dc:creator>
<dcterms:title>A note on the practicality of maximal planar subgraph algorithms</dcterms:title>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2017-01-20T10:00:47Z</dcterms:available>
<dc:contributor>Chimani, Markus</dc:contributor>
<dc:contributor>Klein, Karsten</dc:contributor>
<dc:language>eng</dc:language>
</rdf:Description>
</rdf:RDF> | |
| kops.conferencefield | International Symposium on Graph Drawing and Network Visualization, 19. Sept. 2016 - 21. Sept. 2016, Athens, Greece | deu |
| kops.date.conferenceEnd | 2016-09-21 | eng |
| kops.date.conferenceStart | 2016-09-19 | eng |
| kops.flag.knbibliography | true | |
| kops.location.conference | Athens, Greece | eng |
| kops.sourcefield | HU, Yifan, ed., Martin NÖLLENBURG, ed.. <i>Graph Drawing and Network Visualization : 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers</i>. Cham: Springer International Publishing - Springer, 2016, pp. 357-364. Lecture Notes in Computer Science. 9801. ISBN 978-3-319-50105-5. Available under: doi: 10.1007/978-3-319-50106-2_28 | deu |
| kops.sourcefield.plain | HU, Yifan, ed., Martin NÖLLENBURG, ed.. Graph Drawing and Network Visualization : 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers. Cham: Springer International Publishing - Springer, 2016, pp. 357-364. Lecture Notes in Computer Science. 9801. ISBN 978-3-319-50105-5. Available under: doi: 10.1007/978-3-319-50106-2_28 | deu |
| kops.sourcefield.plain | HU, Yifan, ed., Martin NÖLLENBURG, ed.. Graph Drawing and Network Visualization : 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers. Cham: Springer International Publishing - Springer, 2016, pp. 357-364. Lecture Notes in Computer Science. 9801. ISBN 978-3-319-50105-5. Available under: doi: 10.1007/978-3-319-50106-2_28 | eng |
| kops.title.conference | International Symposium on Graph Drawing and Network Visualization | eng |
| relation.isAuthorOfPublication | 783856d3-db6f-4abb-8969-9efd393896c7 | |
| relation.isAuthorOfPublication.latestForDiscovery | 783856d3-db6f-4abb-8969-9efd393896c7 | |
| source.bibliographicInfo.fromPage | 357 | eng |
| source.bibliographicInfo.seriesNumber | 9801 | eng |
| source.bibliographicInfo.toPage | 364 | eng |
| source.contributor.editor | Hu, Yifan | |
| source.contributor.editor | Nöllenburg, Martin | |
| source.identifier.isbn | 978-3-319-50105-5 | eng |
| source.publisher | Springer International Publishing - Springer | eng |
| source.publisher.location | Cham | eng |
| source.relation.ispartofseries | Lecture Notes in Computer Science | eng |
| source.title | Graph Drawing and Network Visualization : 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers | eng |