2026-10-01T07:51:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26042 2026-09-23T23:58:34Z ddc:004 open_access

How Many Slopes Does Polynomial Area Cost? Bekos, Michael A. Katsanou, Eleni Kindermann, Philipp Pavlidi, Maria Eleni k-bend planar drawings planar slope number area requirements 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael A. Bekos and Eleni Katsanou and Philipp Kindermann and Maria Eleni Pavlidi 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.6 urn:nbn:de:0030-drops-260424 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.6 eng https://creativecommons.org/licenses/by/4.0/legalcode