OASIcs, Volume 13
MEMICS 2009, November 13-15, 2009, Znojmo, Czech Republic
Editors: Petr Hlinený, Václav Matyáš, and Tomáš Vojnar
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guśpiel, Petr Hliněný, Filip Pokrývka, and Marek Sokołowski. Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bergougnoux_et_al:LIPIcs.ISAAC.2023.11, author = {Bergougnoux, Benjamin and Gajarsk\'{y}, Jakub and Gu\'{s}piel, Grzegorz and Hlin\v{e}n\'{y}, Petr and Pokr\'{y}vka, Filip and Soko{\l}owski, Marek}, title = {{Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {11:1--11:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.11}, URN = {urn:nbn:de:0030-drops-193130}, doi = {10.4230/LIPIcs.ISAAC.2023.11}, annote = {Keywords: twin-width, tree-width, excluded grid, sparsity} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Deniz Ağaoğlu Çağırıcı, Onur Çağırıcı, Jan Derbisz, Tim A. Hartmann, Petr Hliněný, Jan Kratochvíl, Tomasz Krawczyk, and Peter Zeman. Recognizing H-Graphs - Beyond Circular-Arc Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{agaoglucagirici_et_al:LIPIcs.MFCS.2023.8, author = {A\u{g}ao\u{g}lu \c{C}a\u{g}{\i}r{\i}c{\i}, Deniz and \c{C}a\u{g}{\i}r{\i}c{\i}, Onur and Derbisz, Jan and Hartmann, Tim A. and Hlin\v{e}n\'{y}, Petr and Kratochv{\'\i}l, Jan and Krawczyk, Tomasz and Zeman, Peter}, title = {{Recognizing H-Graphs - Beyond Circular-Arc Graphs}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {8:1--8:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.8}, URN = {urn:nbn:de:0030-drops-185420}, doi = {10.4230/LIPIcs.MFCS.2023.8}, annote = {Keywords: H-graphs, Intersection Graphs, Helly Property} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Petr Hliněný and Jan Jedelský. Twin-Width of Planar Graphs Is at Most 8, and at Most 6 When Bipartite Planar. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 75:1-75:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{hlineny_et_al:LIPIcs.ICALP.2023.75, author = {Hlin\v{e}n\'{y}, Petr and Jedelsk\'{y}, Jan}, title = {{Twin-Width of Planar Graphs Is at Most 8, and at Most 6 When Bipartite Planar}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {75:1--75:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.75}, URN = {urn:nbn:de:0030-drops-181271}, doi = {10.4230/LIPIcs.ICALP.2023.75}, annote = {Keywords: twin-width, planar graph} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Michael A. Bekos, Giordano Da Lozzo, Petr Hliněný, and Michael Kaufmann. Graph Product Structure for h-Framed Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bekos_et_al:LIPIcs.ISAAC.2022.23, author = {Bekos, Michael A. and Da Lozzo, Giordano and Hlin\v{e}n\'{y}, Petr and Kaufmann, Michael}, title = {{Graph Product Structure for h-Framed Graphs}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {23:1--23:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.23}, URN = {urn:nbn:de:0030-drops-173086}, doi = {10.4230/LIPIcs.ISAAC.2022.23}, annote = {Keywords: Graph product structure theory, h-framed graphs, k-map graphs, queue number, twin-width} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Thekla Hamm and Petr Hliněný. Parameterised Partially-Predrawn Crossing Number. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{hamm_et_al:LIPIcs.SoCG.2022.46, author = {Hamm, Thekla and Hlin\v{e}n\'{y}, Petr}, title = {{Parameterised Partially-Predrawn Crossing Number}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {46:1--46:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.46}, URN = {urn:nbn:de:0030-drops-160547}, doi = {10.4230/LIPIcs.SoCG.2022.46}, annote = {Keywords: Crossing Number, Drawing Extension, Partial Planarity, Parameterised Complexity} }
Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Jakub Balabán and Petr Hliněný. Twin-Width Is Linear in the Poset Width. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{balaban_et_al:LIPIcs.IPEC.2021.6, author = {Balab\'{a}n, Jakub and Hlin\v{e}n\'{y}, Petr}, title = {{Twin-Width Is Linear in the Poset Width}}, booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)}, pages = {6:1--6:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-216-7}, ISSN = {1868-8969}, year = {2021}, volume = {214}, editor = {Golovach, Petr A. and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.6}, URN = {urn:nbn:de:0030-drops-153895}, doi = {10.4230/LIPIcs.IPEC.2021.6}, annote = {Keywords: twin-width, digraph, poset, FO model checking, contraction sequence} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Jan Bok, Jiří Fiala, Petr Hliněný, Nikola Jedličková, and Jan Kratochvíl. Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bok_et_al:LIPIcs.MFCS.2021.21, author = {Bok, Jan and Fiala, Ji\v{r}{\'\i} and Hlin\v{e}n\'{y}, Petr and Jedli\v{c}kov\'{a}, Nikola and Kratochv{\'\i}l, Jan}, title = {{Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {21:1--21:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.21}, URN = {urn:nbn:de:0030-drops-144611}, doi = {10.4230/LIPIcs.MFCS.2021.21}, annote = {Keywords: graph cover, covering projection, semi-edges, multigraphs, complexity} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Deniz Ağaoğlu and Petr Hliněný. Isomorphism Problem for S_d-Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{agaoglu_et_al:LIPIcs.MFCS.2020.4, author = {A\u{g}ao\u{g}lu, Deniz and Hlin\v{e}n\'{y}, Petr}, title = {{Isomorphism Problem for S\underlined-Graphs}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {4:1--4:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.4}, URN = {urn:nbn:de:0030-drops-126754}, doi = {10.4230/LIPIcs.MFCS.2020.4}, annote = {Keywords: intersection graph, isomorphism testing, interval graph, H-graph} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
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)
@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} }
Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)
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)
@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} }
Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Petr Hlineny, Filip Pokrývka, and Bodhayan Roy. FO Model Checking of Geometric Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 19:1-19:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{hlineny_et_al:LIPIcs.IPEC.2017.19, author = {Hlineny, Petr and Pokr\'{y}vka, Filip and Roy, Bodhayan}, title = {{FO Model Checking of Geometric Graphs}}, booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)}, pages = {19:1--19:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-051-4}, ISSN = {1868-8969}, year = {2018}, volume = {89}, editor = {Lokshtanov, Daniel and Nishimura, Naomi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.19}, URN = {urn:nbn:de:0030-drops-85597}, doi = {10.4230/LIPIcs.IPEC.2017.19}, annote = {Keywords: first-order logic, model checking, fixed-parameter tractability, intersection graphs, visibility graphs} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Onur Cagirici, Petr Hlinený, and Bodhayan Roy. On Colourability of Polygon Visibility Graphs. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{cagirici_et_al:LIPIcs.FSTTCS.2017.21, author = {Cagirici, Onur and Hlinen\'{y}, Petr and Roy, Bodhayan}, title = {{On Colourability of Polygon Visibility Graphs}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {21:1--21:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.21}, URN = {urn:nbn:de:0030-drops-83814}, doi = {10.4230/LIPIcs.FSTTCS.2017.21}, annote = {Keywords: polygon visibility graph, graph coloring, NP-completeness} }
Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)
Markus Chimani and Petr Hlinený. Inserting Multiple Edges into a Planar Graph. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{chimani_et_al:LIPIcs.SoCG.2016.30, author = {Chimani, Markus and Hlinen\'{y}, Petr}, title = {{Inserting Multiple Edges into a Planar Graph}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {30:1--30:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-009-5}, ISSN = {1868-8969}, year = {2016}, volume = {51}, editor = {Fekete, S\'{a}ndor and Lubiw, Anna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.30}, URN = {urn:nbn:de:0030-drops-59223}, doi = {10.4230/LIPIcs.SoCG.2016.30}, annote = {Keywords: crossing number, edge insertion, parameterized complexity, path homotopy, funnel algorithm} }
Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)
Petr Hlinený and Marek Dernár. Crossing Number is Hard for Kernelization. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 42:1-42:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{hlineny_et_al:LIPIcs.SoCG.2016.42, author = {Hlinen\'{y}, Petr and Dern\'{a}r, Marek}, title = {{Crossing Number is Hard for Kernelization}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {42:1--42:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-009-5}, ISSN = {1868-8969}, year = {2016}, volume = {51}, editor = {Fekete, S\'{a}ndor and Lubiw, Anna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.42}, URN = {urn:nbn:de:0030-drops-59347}, doi = {10.4230/LIPIcs.SoCG.2016.42}, annote = {Keywords: crossing number; tile crossing number; parameterized complexity; polynomial kernel; cross-composition} }
Feedback for Dagstuhl Publishing