Testing maximal 1-planarity of graphs with a rotation system in linear time (extended abstract)

Peter Eades; Seok Hee Hong; Naoki Katoh; Giuseppe Liotta; Pascal Schweitzer; Yusuke Suzuki

doi:10.1007/978-3-642-36763-2_30

Testing maximal 1-planarity of graphs with a rotation system in linear time (extended abstract)

Peter Eades^*, Seok Hee Hong, Naoki Katoh, Giuseppe Liotta, Pascal Schweitzer, Yusuke Suzuki

^*Corresponding author for this work

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

12 Citations (Scopus)

Abstract

A 1-planar graph is a graph that can be embedded in the plane with at most one crossing per edge. It is known that testing 1-planarity of a graph is NP-complete. A 1-planar embedding of a graph G is maximal if no edge can be added without violating the 1-planarity of G. In this paper we show that the problem of testing maximal 1-planarity of a graph G can be solved in linear time, if a rotation system (i.e., the circular ordering of edges for each vertex) is given. We also prove that there is at most one maximal 1-planar embedding of G that preserves the given rotation system, and our algorithm produces such an embedding in linear time, if it exists.

Original language	English
Title of host publication	Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers
Pages	339-345
Number of pages	7
DOIs	https://doi.org/10.1007/978-3-642-36763-2_30
Publication status	Published - 2013
Event	20th International Symposium on Graph Drawing, GD 2012 - Redmond, WA, United States Duration: 19 Sept 2012 → 21 Sept 2012

Publication series

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

Conference

Conference	20th International Symposium on Graph Drawing, GD 2012
Country/Territory	United States
City	Redmond, WA
Period	19/09/12 → 21/09/12

Access to Document

10.1007/978-3-642-36763-2_30

Cite this

Eades, P., Hong, S. H., Katoh, N., Liotta, G., Schweitzer, P., & Suzuki, Y. (2013). Testing maximal 1-planarity of graphs with a rotation system in linear time (extended abstract). In Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers (pp. 339-345). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7704 LNCS). https://doi.org/10.1007/978-3-642-36763-2_30

Eades, Peter ; Hong, Seok Hee ; Katoh, Naoki et al. / Testing maximal 1-planarity of graphs with a rotation system in linear time (extended abstract). Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers. 2013. pp. 339-345 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1af592dc80a940ef883f44480e1883e6,

title = "Testing maximal 1-planarity of graphs with a rotation system in linear time (extended abstract)",

abstract = "A 1-planar graph is a graph that can be embedded in the plane with at most one crossing per edge. It is known that testing 1-planarity of a graph is NP-complete. A 1-planar embedding of a graph G is maximal if no edge can be added without violating the 1-planarity of G. In this paper we show that the problem of testing maximal 1-planarity of a graph G can be solved in linear time, if a rotation system (i.e., the circular ordering of edges for each vertex) is given. We also prove that there is at most one maximal 1-planar embedding of G that preserves the given rotation system, and our algorithm produces such an embedding in linear time, if it exists.",

author = "Peter Eades and Hong, {Seok Hee} and Naoki Katoh and Giuseppe Liotta and Pascal Schweitzer and Yusuke Suzuki",

year = "2013",

doi = "10.1007/978-3-642-36763-2_30",

language = "English",

isbn = "9783642367625",

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

pages = "339--345",

booktitle = "Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers",

note = "20th International Symposium on Graph Drawing, GD 2012 ; Conference date: 19-09-2012 Through 21-09-2012",

}

Eades, P, Hong, SH, Katoh, N, Liotta, G, Schweitzer, P & Suzuki, Y 2013, Testing maximal 1-planarity of graphs with a rotation system in linear time (extended abstract). in Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7704 LNCS, pp. 339-345, 20th International Symposium on Graph Drawing, GD 2012, Redmond, WA, United States, 19/09/12. https://doi.org/10.1007/978-3-642-36763-2_30

Testing maximal 1-planarity of graphs with a rotation system in linear time (extended abstract). / Eades, Peter; Hong, Seok Hee; Katoh, Naoki et al.
Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers. 2013. p. 339-345 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7704 LNCS).

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

TY - GEN

T1 - Testing maximal 1-planarity of graphs with a rotation system in linear time (extended abstract)

AU - Eades, Peter

AU - Hong, Seok Hee

AU - Katoh, Naoki

AU - Liotta, Giuseppe

AU - Schweitzer, Pascal

AU - Suzuki, Yusuke

PY - 2013

Y1 - 2013

N2 - A 1-planar graph is a graph that can be embedded in the plane with at most one crossing per edge. It is known that testing 1-planarity of a graph is NP-complete. A 1-planar embedding of a graph G is maximal if no edge can be added without violating the 1-planarity of G. In this paper we show that the problem of testing maximal 1-planarity of a graph G can be solved in linear time, if a rotation system (i.e., the circular ordering of edges for each vertex) is given. We also prove that there is at most one maximal 1-planar embedding of G that preserves the given rotation system, and our algorithm produces such an embedding in linear time, if it exists.

AB - A 1-planar graph is a graph that can be embedded in the plane with at most one crossing per edge. It is known that testing 1-planarity of a graph is NP-complete. A 1-planar embedding of a graph G is maximal if no edge can be added without violating the 1-planarity of G. In this paper we show that the problem of testing maximal 1-planarity of a graph G can be solved in linear time, if a rotation system (i.e., the circular ordering of edges for each vertex) is given. We also prove that there is at most one maximal 1-planar embedding of G that preserves the given rotation system, and our algorithm produces such an embedding in linear time, if it exists.

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

U2 - 10.1007/978-3-642-36763-2_30

DO - 10.1007/978-3-642-36763-2_30

M3 - Conference contribution

SN - 9783642367625

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

SP - 339

EP - 345

BT - Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers

T2 - 20th International Symposium on Graph Drawing, GD 2012

Y2 - 19 September 2012 through 21 September 2012

ER -

Eades P, Hong SH, Katoh N, Liotta G, Schweitzer P, Suzuki Y. Testing maximal 1-planarity of graphs with a rotation system in linear time (extended abstract). In Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers. 2013. p. 339-345. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-36763-2_30

Testing maximal 1-planarity of graphs with a rotation system in linear time (extended abstract)

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this