2026-07-24T12:23:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21316 2024-10-28T09:51:05Z ddc:004 open_access

On the Complexity of Recognizing k^+-Real Face Graphs Bekos, Michael A. Di Battista, Giuseppe Di Giacomo, Emilio Didimo, Walter Kaufmann, Michael Montecchiani, Fabrizio Beyond planarity k^+-real face drawings 2-layer drawings recognition algorithm NP-hardness A nonplanar drawing Γ of a graph G divides the plane into topologically connected regions, called faces (or cells). The boundary of each face is formed by vertices, crossings, and edge segments. Given a positive integer k, we say that Γ is a k^+-real face drawing of G if the boundary of each face of Γ contains at least k vertices of G. The study of k^+-real face drawings started in a paper by Binucci et al. (WG 2023), where edge density bounds and relationships with other beyond-planar graph classes are proved. In this paper, we investigate the complexity of recognizing k^+-real face graphs, i.e., graphs that admit a k^+-real face drawing. We study both the general unconstrained scenario and the 2-layer scenario in which the graph is bipartite, the vertices of the two partition sets lie on two distinct horizontal layers, and the edges are straight-line segments. We give NP-completeness results for the unconstrained scenario and efficient recognition algorithms for the 2-layer setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael A. Bekos and Giuseppe Di Battista and Emilio Di Giacomo and Walter Didimo and Michael Kaufmann and Fabrizio Montecchiani 2024 Is Part Of LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2024.32 urn:nbn:de:0030-drops-213167 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.32 eng https://creativecommons.org/licenses/by/4.0/legalcode