On the planar split thickness of graphs

David Eppstein; Philipp Kindermann; Stephen Kobourov; Giuseppe Liotta; Anna Lubiw; Aude Maignan; Debajyoti Mondal; Hamideh Vosoughpour; Sue Whitesides; Stephen Wismath

doi:10.1007/978-3-662-49529-2_30

On the planar split thickness of graphs

David Eppstein, Philipp Kindermann, Stephen Kobourov, Giuseppe Liotta, Anna Lubiw, Aude Maignan, Debajyoti Mondal, Hamideh Vosoughpour, Sue Whitesides, Stephen Wismath

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

Abstract

Motivated by applications in graph drawing and information visualization, we examine the planar split thickness of a graph, that is, the smallest k such that the graph is k-splittable into a planar graph. A k-split operation substitutes a vertex v by at most k new vertices such that each neighbor of v is connected to at least one of the new vertices. We first examine the planar split thickness of complete and complete bipartite graphs. We then prove that it is NP-hard to recognize graphs that are 2-splittable into a planar graph, and show that one can approximate the planar split thickness of a graph within a constant factor. If the treewidth is bounded, then we can even verify k-splittablity in linear time, for a constant k.

Original language	English (US)
Title of host publication	LATIN 2016
Subtitle of host publication	Theoretical Informatics - 12th Latin American Symposium, Proceedings
Editors	Gonzalo Navarro, Evangelos Kranakis, Edgar Chávez
Publisher	Springer-Verlag
Pages	403-415
Number of pages	13
ISBN (Print)	9783662495285
DOIs	https://doi.org/10.1007/978-3-662-49529-2_30
State	Published - 2016
Event	12th Latin American Symposium on Theoretical Informatics, LATIN 2016 - Ensenada, Mexico Duration: Apr 11 2016 → Apr 15 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9644
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	12th Latin American Symposium on Theoretical Informatics, LATIN 2016
Country/Territory	Mexico
City	Ensenada
Period	4/11/16 → 4/15/16

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-662-49529-2_30

Cite this

Eppstein, D., Kindermann, P., Kobourov, S., Liotta, G., Lubiw, A., Maignan, A., Mondal, D., Vosoughpour, H., Whitesides, S., & Wismath, S. (2016). On the planar split thickness of graphs. In G. Navarro, E. Kranakis, & E. Chávez (Eds.), LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Proceedings (pp. 403-415). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9644). Springer-Verlag. https://doi.org/10.1007/978-3-662-49529-2_30

On the planar split thickness of graphs. / Eppstein, David; Kindermann, Philipp; Kobourov, Stephen et al.
LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Proceedings. ed. / Gonzalo Navarro; Evangelos Kranakis; Edgar Chávez. Springer-Verlag, 2016. p. 403-415 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9644).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Eppstein, D, Kindermann, P, Kobourov, S, Liotta, G, Lubiw, A, Maignan, A, Mondal, D, Vosoughpour, H, Whitesides, S & Wismath, S 2016, On the planar split thickness of graphs. in G Navarro, E Kranakis & E Chávez (eds), LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9644, Springer-Verlag, pp. 403-415, 12th Latin American Symposium on Theoretical Informatics, LATIN 2016, Ensenada, Mexico, 4/11/16. https://doi.org/10.1007/978-3-662-49529-2_30

Eppstein D, Kindermann P, Kobourov S, Liotta G, Lubiw A, Maignan A et al. On the planar split thickness of graphs. In Navarro G, Kranakis E, Chávez E, editors, LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Proceedings. Springer-Verlag. 2016. p. 403-415. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-49529-2_30

Eppstein, David ; Kindermann, Philipp ; Kobourov, Stephen et al. / On the planar split thickness of graphs. LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Proceedings. editor / Gonzalo Navarro ; Evangelos Kranakis ; Edgar Chávez. Springer-Verlag, 2016. pp. 403-415 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b2627aa8bff540ffa99e8db94c8244f5,

title = "On the planar split thickness of graphs",

abstract = "Motivated by applications in graph drawing and information visualization, we examine the planar split thickness of a graph, that is, the smallest k such that the graph is k-splittable into a planar graph. A k-split operation substitutes a vertex v by at most k new vertices such that each neighbor of v is connected to at least one of the new vertices. We first examine the planar split thickness of complete and complete bipartite graphs. We then prove that it is NP-hard to recognize graphs that are 2-splittable into a planar graph, and show that one can approximate the planar split thickness of a graph within a constant factor. If the treewidth is bounded, then we can even verify k-splittablity in linear time, for a constant k.",

author = "David Eppstein and Philipp Kindermann and Stephen Kobourov and Giuseppe Liotta and Anna Lubiw and Aude Maignan and Debajyoti Mondal and Hamideh Vosoughpour and Sue Whitesides and Stephen Wismath",

note = "Funding Information: Most of the results of this paper were obtained at the McGill-INRIA-Victoria Workshop on Computational Geometry, Barbados, February 2015. We would like to thank the organizers of these events, as well as many participants for fruitful discussions and suggestions. The first, fourth, sixth, and eighth authors acknowledge the support from NSF grant 1228639, 2012C4E3KT PRIN Italian National Research Project, PEPS egalite project, and NSERC respectively. Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2016.; 12th Latin American Symposium on Theoretical Informatics, LATIN 2016 ; Conference date: 11-04-2016 Through 15-04-2016",

year = "2016",

doi = "10.1007/978-3-662-49529-2_30",

language = "English (US)",

isbn = "9783662495285",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "403--415",

editor = "Gonzalo Navarro and Evangelos Kranakis and Edgar Ch{\'a}vez",

booktitle = "LATIN 2016",

}

TY - GEN

T1 - On the planar split thickness of graphs

AU - Eppstein, David

AU - Kindermann, Philipp

AU - Kobourov, Stephen

AU - Liotta, Giuseppe

AU - Lubiw, Anna

AU - Maignan, Aude

AU - Mondal, Debajyoti

AU - Vosoughpour, Hamideh

AU - Whitesides, Sue

AU - Wismath, Stephen

N1 - Funding Information: Most of the results of this paper were obtained at the McGill-INRIA-Victoria Workshop on Computational Geometry, Barbados, February 2015. We would like to thank the organizers of these events, as well as many participants for fruitful discussions and suggestions. The first, fourth, sixth, and eighth authors acknowledge the support from NSF grant 1228639, 2012C4E3KT PRIN Italian National Research Project, PEPS egalite project, and NSERC respectively. Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2016.

PY - 2016

Y1 - 2016

N2 - Motivated by applications in graph drawing and information visualization, we examine the planar split thickness of a graph, that is, the smallest k such that the graph is k-splittable into a planar graph. A k-split operation substitutes a vertex v by at most k new vertices such that each neighbor of v is connected to at least one of the new vertices. We first examine the planar split thickness of complete and complete bipartite graphs. We then prove that it is NP-hard to recognize graphs that are 2-splittable into a planar graph, and show that one can approximate the planar split thickness of a graph within a constant factor. If the treewidth is bounded, then we can even verify k-splittablity in linear time, for a constant k.

AB - Motivated by applications in graph drawing and information visualization, we examine the planar split thickness of a graph, that is, the smallest k such that the graph is k-splittable into a planar graph. A k-split operation substitutes a vertex v by at most k new vertices such that each neighbor of v is connected to at least one of the new vertices. We first examine the planar split thickness of complete and complete bipartite graphs. We then prove that it is NP-hard to recognize graphs that are 2-splittable into a planar graph, and show that one can approximate the planar split thickness of a graph within a constant factor. If the treewidth is bounded, then we can even verify k-splittablity in linear time, for a constant k.

UR - http://www.scopus.com/inward/record.url?scp=84961683199&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84961683199&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-49529-2_30

DO - 10.1007/978-3-662-49529-2_30

M3 - Conference contribution

AN - SCOPUS:84961683199

SN - 9783662495285

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 403

EP - 415

BT - LATIN 2016

A2 - Navarro, Gonzalo

A2 - Kranakis, Evangelos

A2 - Chávez, Edgar

PB - Springer-Verlag

T2 - 12th Latin American Symposium on Theoretical Informatics, LATIN 2016

Y2 - 11 April 2016 through 15 April 2016

ER -

On the planar split thickness of graphs

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this