Search Results

Documents authored by Mohar, Bojan

Document
DOI: 10.4230/LIPIcs.ISAAC.2024.24
Exact Algorithms for Clustered Planarity with Linear Saturators

Authors: Giordano Da Lozzo, Robert Ganian, Siddharth Gupta, Bojan Mohar, Sebastian Ordyniak, and Meirav Zehavi

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
We study Clustered Planarity with Linear Saturators, which is the problem of augmenting an n-vertex planar graph whose vertices are partitioned into independent sets (called clusters) with paths - one for each cluster - that connect all the vertices in each cluster while maintaining planarity. We show that the problem can be solved in time 2^𝒪(n) for both the variable and fixed embedding case. Moreover, we show that it can be solved in subexponential time 2^𝒪(√n log n) in the fixed embedding case if additionally the input graph is connected. The latter time complexity is tight under the Exponential-Time Hypothesis. We also show that n can be replaced with the vertex cover number of the input graph by providing a linear (resp. polynomial) kernel for the variable-embedding (resp. fixed-embedding) case; these results contrast the NP-hardness of the problem on graphs of bounded treewidth (and even on trees). Finally, we complement known lower bounds for the problem by showing that Clustered Planarity with Linear Saturators is NP-hard even when the number of clusters is at most 3, thus excluding the algorithmic use of the number of clusters as a parameter.
Cite as

Giordano Da Lozzo, Robert Ganian, Siddharth Gupta, Bojan Mohar, Sebastian Ordyniak, and Meirav Zehavi. Exact Algorithms for Clustered Planarity with Linear Saturators. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dalozzo_et_al:LIPIcs.ISAAC.2024.24,
  author =	{Da Lozzo, Giordano and Ganian, Robert and Gupta, Siddharth and Mohar, Bojan and Ordyniak, Sebastian and Zehavi, Meirav},
  title =	{{Exact Algorithms for Clustered Planarity with Linear Saturators}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{24:1--24:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.24},
  URN =		{urn:nbn:de:0030-drops-221513},
  doi =		{10.4230/LIPIcs.ISAAC.2024.24},
  annote =	{Keywords: Clustered planarity, independent c-graphs, path saturation, graph drawing}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.86
Automorphisms and Isomorphisms of Maps in Linear Time

Authors: Ken-ichi Kawarabayashi, Bojan Mohar, Roman Nedela, and Peter Zeman

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
A map is a 2-cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. An automorphism of a map can be thought of as a permutation of the vertices which preserves the vertex-edge-face incidences in the embedding. When the underlying surface is orientable, every automorphism of a map determines an angle-preserving homeomorphism of the surface. While it is conjectured that there is no "truly subquadratic" algorithm for testing map isomorphism for unconstrained genus, we present a linear-time algorithm for computing the generators of the automorphism group of a map, parametrized by the genus of the underlying surface. The algorithm applies a sequence of local reductions and produces a uniform map, while preserving the automorphism group. The automorphism group of the original map can be reconstructed from the automorphism group of the uniform map in linear time. We also extend the algorithm to non-orientable surfaces by making use of the antipodal double-cover.
Cite as

Ken-ichi Kawarabayashi, Bojan Mohar, Roman Nedela, and Peter Zeman. Automorphisms and Isomorphisms of Maps in Linear Time. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 86:1-86:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kawarabayashi_et_al:LIPIcs.ICALP.2021.86,
  author =	{Kawarabayashi, Ken-ichi and Mohar, Bojan and Nedela, Roman and Zeman, Peter},
  title =	{{Automorphisms and Isomorphisms of Maps in Linear Time}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{86:1--86:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.86},
  URN =		{urn:nbn:de:0030-drops-141558},
  doi =		{10.4230/LIPIcs.ICALP.2021.86},
  annote =	{Keywords: maps on surfaces, automorphisms, isomorphisms, algorithm}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.14
Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c <= 12

Authors: Drago Bokal, Zdeněk Dvořák, Petr Hliněný, Jesús Leaños, Bojan Mohar, and Tilo Wiedera

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For every fixed pair of integers with c >= 13 and d >= 1, we give first explicit constructions of c-crossing-critical graphs containing a vertex of degree greater than d. We also show that such unbounded degree constructions do not exist for c <=12, precisely, that there exists a constant D such that every c-crossing-critical graph with c <=12 has maximum degree at most D. Hence, the bounded maximum degree conjecture of c-crossing-critical graphs, which was generally disproved in 2010 by Dvořák and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values c <=12.
Cite as

Drago Bokal, Zdeněk Dvořák, Petr Hliněný, Jesús Leaños, Bojan Mohar, and Tilo Wiedera. Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c <= 12. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bokal_et_al:LIPIcs.SoCG.2019.14,
  author =	{Bokal, Drago and Dvo\v{r}\'{a}k, Zden\v{e}k and Hlin\v{e}n\'{y}, Petr and Lea\~{n}os, Jes\'{u}s and Mohar, Bojan and Wiedera, Tilo},
  title =	{{Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c \langle= 12}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.14},
  URN =		{urn:nbn:de:0030-drops-104183},
  doi =		{10.4230/LIPIcs.SoCG.2019.14},
  annote =	{Keywords: graph drawing, crossing number, crossing-critical, zip product}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.27
Embedding Graphs into Two-Dimensional Simplicial Complexes

Authors: Éric Colin de Verdière, Thomas Magnard, and Bojan Mohar

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We consider the problem of deciding whether an input graph G admits a topological embedding into a two-dimensional simplicial complex C. This problem includes, among others, the embeddability problem of a graph on a surface and the topological crossing number of a graph, but is more general. The problem is NP-complete when C is part of the input, and we give a polynomial-time algorithm if the complex C is fixed. Our strategy is to reduce the problem to an embedding extension problem on a surface, which has the following form: Given a subgraph H' of a graph G', and an embedding of H' on a surface S, can that embedding be extended to an embedding of G' on S? Such problems can be solved, in turn, using a key component in Mohar's algorithm to decide the embeddability of a graph on a fixed surface (STOC 1996, SIAM J. Discr. Math. 1999).
Cite as

Éric Colin de Verdière, Thomas Magnard, and Bojan Mohar. Embedding Graphs into Two-Dimensional Simplicial Complexes. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{verdiere_et_al:LIPIcs.SoCG.2018.27,
  author =	{Verdi\`{e}re, \'{E}ric Colin de and Magnard, Thomas and Mohar, Bojan},
  title =	{{Embedding Graphs into Two-Dimensional Simplicial Complexes}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.27},
  URN =		{urn:nbn:de:0030-drops-87401},
  doi =		{10.4230/LIPIcs.SoCG.2018.27},
  annote =	{Keywords: computational topology, embedding, simplicial complex, graph, surface}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.33
Structure and Generation of Crossing-Critical Graphs

Authors: Zdenek Dvorák, Petr Hlinený, and Bojan Mohar

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For c=1 there are only two such graphs without degree-2 vertices, K_5 and K_{3,3}, but for any fixed c>1 there exist infinitely many c-crossing-critical graphs. It has been previously shown that c-crossing-critical graphs have bounded path-width and contain only a bounded number of internally disjoint paths between any two vertices. We expand on these results, providing a more detailed description of the structure of crossing-critical graphs. On the way towards this description, we prove a new structural characterisation of plane graphs of bounded path-width. Then we show that every c-crossing-critical graph can be obtained from a c-crossing-critical graph of bounded size by replicating bounded-size parts that already appear in narrow "bands" or "fans" in the graph. This also gives an algorithm to generate all the c-crossing-critical graphs of at most given order n in polynomial time per each generated graph.
Cite as

Zdenek Dvorák, Petr Hlinený, and Bojan Mohar. Structure and Generation of Crossing-Critical Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.SoCG.2018.33,
  author =	{Dvor\'{a}k, Zdenek and Hlinen\'{y}, Petr and Mohar, Bojan},
  title =	{{Structure and Generation of Crossing-Critical Graphs}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{33:1--33:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.33},
  URN =		{urn:nbn:de:0030-drops-87460},
  doi =		{10.4230/LIPIcs.SoCG.2018.33},
  annote =	{Keywords: crossing number, crossing-critical, path-width, exhaustive generation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.27
Graphic TSP in Cubic Graphs

Authors: Zdenek Dvorák, Daniel Král, and Bojan Mohar

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We present a polynomial-time 9/7-approximation algorithm for the graphic TSP for cubic graphs, which improves the previously best approximation factor of 1.3 for 2-connected cubic graphs and drops the requirement of 2-connectivity at the same time. To design our algorithm, we prove that every simple 2-connected cubic n-vertex graph contains a spanning closed walk of length at most 9n/7-1, and that such a walk can be found in polynomial time.
Cite as

Zdenek Dvorák, Daniel Král, and Bojan Mohar. Graphic TSP in Cubic Graphs. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 27:1-27:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.STACS.2017.27,
  author =	{Dvor\'{a}k, Zdenek and Kr\'{a}l, Daniel and Mohar, Bojan},
  title =	{{Graphic TSP in Cubic Graphs}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{27:1--27:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.27},
  URN =		{urn:nbn:de:0030-drops-70068},
  doi =		{10.4230/LIPIcs.STACS.2017.27},
  annote =	{Keywords: Graphic TSP, approximation algorithms, cubic graphs}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact