2026-07-24T17:25:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24996 2026-02-09T07:52:39Z ddc:004 open_access

The Bend Number of Cocomparability Graphs Antić, Todor Jelínek, Vit Pergel, Martin Schröder, Felix Stumpf, Peter Valtr, Pavel Intersection Graphs Bend Number Piecewise Linear Functions Graph Class Hierarchy Cocomparability Graphs Permutation Graphs Poset Dimension We introduce a new complexity measure for cocomparability graphs of posets or in other words, intersection graphs of piecewise linear functions, the bend number. We prove that cocomparability graphs of bounded bend number are not too plentiful and give two hierarchies of classes of cocomparability graphs, depending on whether the piecewise linear functions are restricted to slopes of ±1 (diagonal case) or not (general case). These hierarchies give a gradation between permutation graphs and cocomparability graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Todor Antić and Vit Jelínek and Martin Pergel and Felix Schröder and Peter Stumpf and Pavel Valtr 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.10 urn:nbn:de:0030-drops-249963 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.10 eng https://creativecommons.org/licenses/by/4.0/legalcode