Recognizing hyperelliptic graphs in polynomial time

Jelco M. Bodewes; Hans L. Bodlaender; Gunther Cornelissen; Marieke van der Wegen

doi:10.1007/978-3-030-00256-5_5

Recognizing hyperelliptic graphs in polynomial time

Jelco M. Bodewes, Hans L. Bodlaender, Gunther Cornelissen, Marieke van der Wegen^*

^*Corresponding author for this work

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

Abstract

Based on analogies between algebraic curves and graphs, Baker and Norine introduced divisorial gonality, a graph parameter for multigraphs related to treewidth, multigraph algorithms and number theory. We consider so-called hyperelliptic graphs (multigraphs of gonality 2) and provide a safe and complete set of reduction rules for such multigraphs, showing that we can recognize hyperelliptic graphs in time O(n log n+ m), where n is the number of vertices and m the number of edges of the multigraph. A corollary is that we can decide with the same runtime whether a two-edge-connected graph G admits an involution σ such that the quotient G/ ⟨ σ⟩ is a tree.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings
Publisher	Springer
Pages	52-64
Number of pages	13
ISBN (Print)	9783030002558
DOIs	https://doi.org/10.1007/978-3-030-00256-5_5
Publication status	Published - 1 Jan 2018
Event	44th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2018 - Cottbus, Germany Duration: 27 Jun 2018 → 29 Jun 2018

Publication series

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

Conference

Conference	44th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2018
Country/Territory	Germany
City	Cottbus
Period	27/06/18 → 29/06/18

Funding

H. L. Bodlaender—This author was partially supported by the NETWORKS project, funded by the Netherlands Organisation for Scientific Research.

Access to Document

10.1007/978-3-030-00256-5_5

Recognizing_hyperelliptic_graphs__WG_versie_Accepted author manuscript, 326 KBLicence: Unspecified
Bodewes2018_Chapter_RecognizingHyperellipticGraphsFinal published version, 1.78 MB

Cite this

Bodewes, J. M., Bodlaender, H. L., Cornelissen, G., & van der Wegen, M. (2018). Recognizing hyperelliptic graphs in polynomial time. In Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings (pp. 52-64). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11159 LNCS). Springer. https://doi.org/10.1007/978-3-030-00256-5_5

Bodewes, Jelco M. ; Bodlaender, Hans L. ; Cornelissen, Gunther et al. / Recognizing hyperelliptic graphs in polynomial time. Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings. Springer, 2018. pp. 52-64 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{cc7f26d76c9e44379a518dc28daa1828,

title = "Recognizing hyperelliptic graphs in polynomial time",

abstract = "Based on analogies between algebraic curves and graphs, Baker and Norine introduced divisorial gonality, a graph parameter for multigraphs related to treewidth, multigraph algorithms and number theory. We consider so-called hyperelliptic graphs (multigraphs of gonality 2) and provide a safe and complete set of reduction rules for such multigraphs, showing that we can recognize hyperelliptic graphs in time O(n log n+ m), where n is the number of vertices and m the number of edges of the multigraph. A corollary is that we can decide with the same runtime whether a two-edge-connected graph G admits an involution σ such that the quotient G/ ⟨ σ⟩ is a tree.",

author = "Bodewes, {Jelco M.} and Bodlaender, {Hans L.} and Gunther Cornelissen and {van der Wegen}, Marieke",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-030-00256-5_5",

language = "English",

isbn = "9783030002558",

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

publisher = "Springer",

pages = "52--64",

booktitle = "Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings",

note = "44th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2018 ; Conference date: 27-06-2018 Through 29-06-2018",

}

Bodewes, JM, Bodlaender, HL , Cornelissen, G & van der Wegen, M 2018, Recognizing hyperelliptic graphs in polynomial time. in Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11159 LNCS, Springer, pp. 52-64, 44th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2018, Cottbus, Germany, 27/06/18. https://doi.org/10.1007/978-3-030-00256-5_5

Recognizing hyperelliptic graphs in polynomial time. / Bodewes, Jelco M.; Bodlaender, Hans L.; Cornelissen, Gunther et al.
Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings. Springer, 2018. p. 52-64 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11159 LNCS).

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

TY - GEN

T1 - Recognizing hyperelliptic graphs in polynomial time

AU - Bodewes, Jelco M.

AU - Bodlaender, Hans L.

AU - Cornelissen, Gunther

AU - van der Wegen, Marieke

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Based on analogies between algebraic curves and graphs, Baker and Norine introduced divisorial gonality, a graph parameter for multigraphs related to treewidth, multigraph algorithms and number theory. We consider so-called hyperelliptic graphs (multigraphs of gonality 2) and provide a safe and complete set of reduction rules for such multigraphs, showing that we can recognize hyperelliptic graphs in time O(n log n+ m), where n is the number of vertices and m the number of edges of the multigraph. A corollary is that we can decide with the same runtime whether a two-edge-connected graph G admits an involution σ such that the quotient G/ ⟨ σ⟩ is a tree.

AB - Based on analogies between algebraic curves and graphs, Baker and Norine introduced divisorial gonality, a graph parameter for multigraphs related to treewidth, multigraph algorithms and number theory. We consider so-called hyperelliptic graphs (multigraphs of gonality 2) and provide a safe and complete set of reduction rules for such multigraphs, showing that we can recognize hyperelliptic graphs in time O(n log n+ m), where n is the number of vertices and m the number of edges of the multigraph. A corollary is that we can decide with the same runtime whether a two-edge-connected graph G admits an involution σ such that the quotient G/ ⟨ σ⟩ is a tree.

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

U2 - 10.1007/978-3-030-00256-5_5

DO - 10.1007/978-3-030-00256-5_5

M3 - Conference contribution

AN - SCOPUS:85053475695

SN - 9783030002558

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

SP - 52

EP - 64

BT - Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings

PB - Springer

T2 - 44th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2018

Y2 - 27 June 2018 through 29 June 2018

ER -

Bodewes JM, Bodlaender HL , Cornelissen G , van der Wegen M. Recognizing hyperelliptic graphs in polynomial time. In Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Proceedings. Springer. 2018. p. 52-64. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-00256-5_5

Recognizing hyperelliptic graphs in polynomial time

Abstract

Publication series

Conference

Funding

Access to Document

Other files and links

Fingerprint

Cite this