5 Search Results for "Brückner, Guido"

Document
DOI: 10.4230/LIPIcs.SWAT.2026.6
How Many Slopes Does Polynomial Area Cost?

Authors: Michael A. Bekos, Eleni Katsanou, Philipp Kindermann, and Maria Eleni Pavlidi

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
In this work, we study the interplay between the number of slopes, the number of bends per edge, and the area requirements for planar drawings of bounded-degree graphs. Our motivation stems from the fact that, while numerous algorithms produce planar drawings with few slopes for graphs of relatively small degree in polynomial area, existing approaches for higher-degree graphs often require super-polynomial area. We address this gap in the literature by presenting new constructions that yield polynomial-area drawings with few bends per edge while slightly increasing the required number of slopes, thereby providing the first systematic study of slopes, bends and area trade-offs.
Cite as

Michael A. Bekos, Eleni Katsanou, Philipp Kindermann, and Maria Eleni Pavlidi. How Many Slopes Does Polynomial Area Cost?. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.SWAT.2026.6,
  author =	{Bekos, Michael A. and Katsanou, Eleni and Kindermann, Philipp and Pavlidi, Maria Eleni},
  title =	{{How Many Slopes Does Polynomial Area Cost?}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.6},
  URN =		{urn:nbn:de:0030-drops-260424},
  doi =		{10.4230/LIPIcs.SWAT.2026.6},
  annote =	{Keywords: k-bend planar drawings, planar slope number, area requirements}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.25
Structural Parameterizations of Simultaneous Planarity

Authors: Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Matthias Pfretzschner, and Ignaz Rutter

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Given a set of graphs on the same vertex set, the problem Simultaneous Embedding With Fixed Edges (SEFE) asks, whether there exist planar drawings of all input graphs, such that every pair of drawings coincides on their shared subgraph. It is known that SEFE is NP-complete [Elisabeth Gassner et al., 2006], even in the so-called sunflower case, where all pairs of input graphs have the same shared graph G_∩ [Marcus Schaefer, 2012]. Fink, Pfretzschner, and Rutter [Simon D. Fink et al., 2023] recently initiated the study of the parameterized complexity of SEFE in the sunflower case, mainly focusing on structural parameters of G_∩. In this work, we shift the focus towards parameters of the union graph G_∪ that contains the edges of all input graphs. On the positive side, we establish fixed-parameter tractability for the problem with respect to the feedback edge set number of G_∪. We complement this result by showing that it, surprisingly, remains NP-complete even if G_∪ has constant vertex cover number. These results settle two open questions posed by Fink et al. [Simon D. Fink et al., 2023].
Cite as

Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Matthias Pfretzschner, and Ignaz Rutter. Structural Parameterizations of Simultaneous Planarity. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{depian_et_al:LIPIcs.ISAAC.2025.25,
  author =	{Depian, Thomas and Fink, Simon D. and Firbas, Alexander and Ganian, Robert and Pfretzschner, Matthias and Rutter, Ignaz},
  title =	{{Structural Parameterizations of Simultaneous Planarity}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.25},
  URN =		{urn:nbn:de:0030-drops-249332},
  doi =		{10.4230/LIPIcs.ISAAC.2025.25},
  annote =	{Keywords: SEFE, Simultaneous Planarity, Fixed-Parameter Tractability, NP-hardness}
}
Document
Survey
DOI: 10.4230/TGDK.3.2.1
Resilience in Knowledge Graph Embeddings

Authors: Arnab Sharma, N'Dah Jean Kouagou, and Axel-Cyrille Ngonga Ngomo

Published in: TGDK, Volume 3, Issue 2 (2025). Transactions on Graph Data and Knowledge, Volume 3, Issue 2

Abstract
In recent years, knowledge graphs have gained interest and witnessed widespread applications in various domains, such as information retrieval, question-answering, recommendation systems, amongst others. Large-scale knowledge graphs to this end have demonstrated their utility in effectively representing structured knowledge. To further facilitate the application of machine learning techniques, knowledge graph embedding models have been developed. Such models can transform entities and relationships within knowledge graphs into vectors. However, these embedding models often face challenges related to noise, missing information, distribution shift, adversarial attacks, etc. This can lead to sub-optimal embeddings and incorrect inferences, thereby negatively impacting downstream applications. While the existing literature has focused so far on adversarial attacks on KGE models, the challenges related to the other critical aspects remain unexplored. In this paper, we, first of all, give a unified definition of resilience, encompassing several factors such as generalisation, in-distribution generalization, distribution adaption, and robustness. After formalizing these concepts for machine learning in general, we define them in the context of knowledge graphs. To find the gap in the existing works on resilience in the context of knowledge graphs, we perform a systematic survey, taking into account all these aspects mentioned previously. Our survey results show that most of the existing works focus on a specific aspect of resilience, namely robustness. After categorizing such works based on their respective aspects of resilience, we discuss the challenges and future research directions.
Cite as

Arnab Sharma, N'Dah Jean Kouagou, and Axel-Cyrille Ngonga Ngomo. Resilience in Knowledge Graph Embeddings. In Transactions on Graph Data and Knowledge (TGDK), Volume 3, Issue 2, pp. 1:1-1:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{sharma_et_al:TGDK.3.2.1,
  author =	{Sharma, Arnab and Kouagou, N'Dah Jean and Ngomo, Axel-Cyrille Ngonga},
  title =	{{Resilience in Knowledge Graph Embeddings}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{1:1--1:38},
  ISSN =	{2942-7517},
  year =	{2025},
  volume =	{3},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.3.2.1},
  URN =		{urn:nbn:de:0030-drops-248117},
  doi =		{10.4230/TGDK.3.2.1},
  annote =	{Keywords: Knowledge graphs, Resilience, Robustness}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.25
Extending Partial Representations of Circle Graphs in Near-Linear Time

Authors: Guido Brückner, Ignaz Rutter, and Peter Stumpf

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
The partial representation extension problem generalizes the recognition problem for geometric intersection graphs. The input consists of a graph G, a subgraph H ⊆ G and a representation H of H. The question is whether G admits a representation G whose restriction to H is H. We study this question for circle graphs, which are intersection graphs of chords of a circle. Their representations are called chord diagrams. We show that for a graph with n vertices and m edges the partial representation extension problem can be solved in O((n + m) α(n + m)) time, where α is the inverse Ackermann function. This improves over an O(n³)-time algorithm by Chaplick, Fulek and Klavík [2019]. The main technical contributions are a canonical way of orienting chord diagrams and a novel compact representation of the set of all canonically oriented chord diagrams that represent a given circle graph G, which is of independent interest.
Cite as

Guido Brückner, Ignaz Rutter, and Peter Stumpf. Extending Partial Representations of Circle Graphs in Near-Linear Time. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bruckner_et_al:LIPIcs.MFCS.2022.25,
  author =	{Br\"{u}ckner, Guido and Rutter, Ignaz and Stumpf, Peter},
  title =	{{Extending Partial Representations of Circle Graphs in Near-Linear Time}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.25},
  URN =		{urn:nbn:de:0030-drops-168233},
  doi =		{10.4230/LIPIcs.MFCS.2022.25},
  annote =	{Keywords: circle graphs, partial representation extension, split decomposition tree, recognition algorithm}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.8
An SPQR-Tree-Like Embedding Representation for Level Planarity

Authors: Guido Brückner and Ignaz Rutter

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
An SPQR-tree is a data structure that efficiently represents all planar embeddings of a biconnected planar graph. It is a key tool in a number of constrained planarity testing algorithms, which seek a planar embedding of a graph subject to some given set of constraints. We develop an SPQR-tree-like data structure that represents all level-planar embeddings of a biconnected level graph with a single source, called the LP-tree, and give a simple algorithm to compute it in linear time. Moreover, we show that LP-trees can be used to adapt three constrained planarity algorithms to the level-planar case by using them as a drop-in replacement for SPQR-trees.
Cite as

Guido Brückner and Ignaz Rutter. An SPQR-Tree-Like Embedding Representation for Level Planarity. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bruckner_et_al:LIPIcs.ISAAC.2020.8,
  author =	{Br\"{u}ckner, Guido and Rutter, Ignaz},
  title =	{{An SPQR-Tree-Like Embedding Representation for Level Planarity}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.8},
  URN =		{urn:nbn:de:0030-drops-133526},
  doi =		{10.4230/LIPIcs.ISAAC.2020.8},
  annote =	{Keywords: SPQR-tree, Level planarity, Partial drawings, Simultaneous drawings}
}
  • Refine by Type
  • 5 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 2 2025
  • 1 2022
  • 1 2020

  • Refine by Author
  • 3 Rutter, Ignaz
  • 2 Brückner, Guido
  • 1 Bekos, Michael A.
  • 1 Depian, Thomas
  • 1 Fink, Simon D.
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs
  • 1 TGDK

  • Refine by Classification
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Computing methodologies → Reasoning about belief and knowledge
  • 1 Human-centered computing → Graph drawings
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 1 Fixed-Parameter Tractability
  • 1 Knowledge graphs
  • 1 Level planarity
  • 1 NP-hardness
  • 1 Partial drawings
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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