DROPS

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

Poster Abstract

DOI: 10.4230/LIPIcs.GD.2025.49

Defective Linear Layouts of Graphs (Poster Abstract)

Authors: Michael A. Bekos, Carla Binucci, Emilio Di Giacomo, Walter Didimo, Luca Grilli, Maria Eleni Pavlidi, Alessandra Tappini, and Alexandra Weinberger

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract

A linear layout of a graph defines a total order of the vertices and partitions the edges into either stacks or queues, i.e., crossing-free and non-nested sets of edges along the order, respectively. In this work, we study defective linear layouts that allow forbidden patterns among edges of the same set. Our focus is on k-defective stack layouts and k-defective queue layouts, in which the conflict graph representing the forbidden patterns among the edges of each stack or queue has maximum degree at most k.

Cite as

Michael A. Bekos, Carla Binucci, Emilio Di Giacomo, Walter Didimo, Luca Grilli, Maria Eleni Pavlidi, Alessandra Tappini, and Alexandra Weinberger. Defective Linear Layouts of Graphs (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 49:1-49:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.GD.2025.49,
  author =	{Bekos, Michael A. and Binucci, Carla and Di Giacomo, Emilio and Didimo, Walter and Grilli, Luca and Pavlidi, Maria Eleni and Tappini, Alessandra and Weinberger, Alexandra},
  title =	{{Defective Linear Layouts of Graphs}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{49:1--49:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.49},
  URN =		{urn:nbn:de:0030-drops-250350},
  doi =		{10.4230/LIPIcs.GD.2025.49},
  annote =	{Keywords: Linear layouts, stack layouts, queue layouts, defective layouts}
}

Search Results

Documents authored by Pavlidi, Maria Eleni

How Many Slopes Does Polynomial Area Cost?

Abstract

Cite as

Defective Linear Layouts of Graphs (Poster Abstract)

Abstract

Cite as

Thanks for your feedback!

Could not send message