Sieper, Marie Diana - Chair of Computer Science I

Marie Diana Sieper

Lehrstuhl für Informatik I
Universität Würzburg
Am Hubland

97074 Würzburg

Deutschland

Building: M4

Room: 1.004

Email: marie.sieper@uni-wuerzburg.de

Teaching

Winter 2025:

Organized Seminar: Algorithmics

Sommer 2025:

Exercises in Algorithmic Graph Theory

Winter 2024:

Organized Seminar: Algorithmics

Sommer 2024:

Exercises in Exact Algorithms

Winter 2023:

Exercises in Approximation Algorithms

Sommer 2023:

Exercises in Algorithms for Geographic Information Systems

Winter 2022:

Exercises in Approximation Algorithms

Sommer 2022:

Exercises in Visualization of Graphs

Publications

2025[ to top ]

Eliminating Majority Illusion. Foivos Fioravantes, Abhiruk Lahiri, Antonio Lauerbach, Lluís Sabater, Marie Diana Sieper, and Samuel Wolf. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, of AAMAS ’25, S. Das, A. Nowé, Y. Vorobeychik (eds.), pp. 749–757. International Foundation for Autonomous Agents and Multiagent Systems, 2025.
- [ BibTeX ]
- [ URL ]
- [ DOI ]
@inproceedings{fllssw-emi-2025, author = {Fioravantes, Foivos and Lahiri, Abhiruk and Lauerbach, Antonio and Sabater, Lluís and Sieper, Marie Diana and Wolf, Samuel}, booktitle = {Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems}, editor = {Das, Sanmay and Nowé, Ann and Vorobeychik, Yevgeniy}, keywords = {myown}, pages = {749–757}, publisher = {International Foundation for Autonomous Agents and Multiagent Systems}, series = {AAMAS '25}, title = {Eliminating Majority Illusion}, year = 2025 }

2024[ to top ]

Constrained Level Planarity Is FPT with Respect to the Vertex Cover Number. Boris Klemz and Marie Diana Sieper. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), Vol. 297 of Leibniz International Proceedings in Informatics (LIPIcs), K. Bringmann, M. Grohe, G. Puppis, O. Svensson (eds.), pp. 99:1–99:17. Schloss Dagstuhl -- Leibniz-Zentrum f{ü}r Informatik, Dagstuhl, Germany, 2024.
- [ BibTeX ]
- [ DOI ]
@inproceedings{klemz_et_al:LIPIcs.ICALP.2024.99, address = {Dagstuhl, Germany}, annote = {Keywords: Parameterized Complexity, Graph Drawing, Planar Poset Diagram, Level Planarity, Constrained Level Planarity, Vertex Cover, FPT, Computational Geometry}, author = {Klemz, Boris and Sieper, Marie Diana}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, keywords = {myown}, pages = {99:1–99:17}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum f{\"u}r Informatik}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, title = {Constrained Level Planarity Is FPT with Respect to the Vertex Cover Number}, volume = 297, year = 2024 }
Constrained and Ordered Level Planarity Parameterized by the Number of Levels. Vacláv Blazej, Boris Klemz, Felix Klesen, Marie Diana Sieper, Alexander Wolff, and Johannes Zink. In 40th International Symposium on Computational Geometry (SoCG 2024), Vol. 293 of LIPIcs, W. Mulzer, J. M. Phillips (eds.), pp. 20:1–20:16. Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2024.
- [ BibTeX ]
- [ URL ]
- [ DOI ]
@inproceedings{blazej_et_al:LIPIcs.SoCG.2024.20, address = {Dagstuhl, Germany}, annote = {Keywords: Parameterized Complexity, Graph Drawing, XNLP, XP, W\lbrackt\rbrack-hard, Level Planarity, Planar Poset Diagram, Computational Geometry}, author = {Blazej, Vacláv and Klemz, Boris and Klesen, Felix and Sieper, Marie Diana and Wolff, Alexander and Zink, Johannes}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, editor = {Mulzer, Wolfgang and Phillips, Jeff M.}, keywords = {myown}, pages = {20:1–20:16}, publisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik}, series = {LIPIcs}, title = {Constrained and Ordered Level Planarity Parameterized by the Number of Levels}, volume = 293, year = 2024 }
Morphing Graph Drawings in the Presence of Point Obstacles. Oksana Firman, Tim Hegemann, Boris Klemz, Felix Klesen, Marie Diana Sieper, Alexander Wolff, and Johannes Zink. In SOFSEM 2024: Theory and Practice of Computer Science, Vol. 14519 of Lecture Notes in Computer Science, H. Fernau, S. Gaspers, R. Klasing (eds.), pp. 240–254. Springer Nature Switzerland, Cham, 2024.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
A crossing-free morph is a continuous deformation between two graph drawings that preserves straight-line pairwise noncrossing edges. Motivated by applications in 3D morphing problems, we initiate the study of morphing graph drawings in the plane in the presence of stationary point obstacles, which need to be avoided throughout the deformation. As our main result, we prove that it is NP-hard to decide whether such an obstacle-avoiding 2D morph between two given drawings of the same graph exists. This is in sharp contrast to the classical case without obstacles, where there is an efficiently verifiable (necessary and sufficient) criterion for the existence of a morph.

@inproceedings{10.1007/978-3-031-52113-3_17, abstract = {A crossing-free morph is a continuous deformation between two graph drawings that preserves straight-line pairwise noncrossing edges. Motivated by applications in 3D morphing problems, we initiate the study of morphing graph drawings in the plane in the presence of stationary point obstacles, which need to be avoided throughout the deformation. As our main result, we prove that it is NP-hard to decide whether such an obstacle-avoiding 2D morph between two given drawings of the same graph exists. This is in sharp contrast to the classical case without obstacles, where there is an efficiently verifiable (necessary and sufficient) criterion for the existence of a morph.}, address = {Cham}, author = {Firman, Oksana and Hegemann, Tim and Klemz, Boris and Klesen, Felix and Sieper, Marie Diana and Wolff, Alexander and Zink, Johannes}, booktitle = {SOFSEM 2024: Theory and Practice of Computer Science}, editor = {Fernau, Henning and Gaspers, Serge and Klasing, Ralf}, keywords = {myown}, pages = {240–254}, publisher = {Springer Nature Switzerland}, series = {Lecture Notes in Computer Science}, title = {Morphing Graph Drawings in the Presence of Point Obstacles}, volume = 14519, year = 2024 }

2023[ to top ]

Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem. Walter Didimo, Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Stephen Kobourov, and Marie Diana Sieper. In Graph Drawing and Network Visualization, Vol. 14466 of Lecture Notes in Computer Science, M. A. Bekos, M. Chimani (eds.), pp. 189–202. Springer Nature Switzerland, Cham, 2023.
- [ Abstract ]
- [ BibTeX ]
- [ DOI ]
A vertex of a plane digraph is bimodal if all its incoming edges (and hence all its outgoing edges) are consecutive in the cyclic order around it. A plane digraph is bimodal if all its vertices are bimodal. Bimodality is at the heart of many types of graph layouts, such as upward drawings, level-planar drawings, and L-drawings. If the graph is not bimodal, the Maximum Bimodal Subgraph (MBS) problem asks for an embedding-preserving bimodal subgraph with the maximum number of edges. We initiate the study of the MBS problem from the parameterized complexity perspective with two main results: (i) we describe an FPT algorithm parameterized by the branchwidth (and hence by the treewidth) of the graph; (ii) we establish that MBS parameterized by the number of non-bimodal vertices admits a polynomial kernel. As the byproduct of these results, we obtain a subexponential FPT algorithm and an efficient polynomial-time approximation scheme for MBS.

@inproceedings{10.1007/978-3-031-49275-4_13, abstract = {A vertex of a plane digraph is bimodal if all its incoming edges (and hence all its outgoing edges) are consecutive in the cyclic order around it. A plane digraph is bimodal if all its vertices are bimodal. Bimodality is at the heart of many types of graph layouts, such as upward drawings, level-planar drawings, and L-drawings. If the graph is not bimodal, the Maximum Bimodal Subgraph (MBS) problem asks for an embedding-preserving bimodal subgraph with the maximum number of edges. We initiate the study of the MBS problem from the parameterized complexity perspective with two main results: (i) we describe an FPT algorithm parameterized by the branchwidth (and hence by the treewidth) of the graph; (ii) we establish that MBS parameterized by the number of non-bimodal vertices admits a polynomial kernel. As the byproduct of these results, we obtain a subexponential FPT algorithm and an efficient polynomial-time approximation scheme for MBS.}, address = {Cham}, author = {Didimo, Walter and Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Kobourov, Stephen and Sieper, Marie Diana}, booktitle = {Graph Drawing and Network Visualization}, editor = {Bekos, Michael A. and Chimani, Markus}, keywords = {myown}, pages = {189–202}, publisher = {Springer Nature Switzerland}, series = {Lecture Notes in Computer Science}, title = {Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem}, volume = 14466, year = 2023 }

Marie Diana Sieper, M.Sc.

Marie Diana Sieper

Teaching

Publications

Picture credits