{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:32:13Z","timestamp":1740133933478,"version":"3.37.3"},"reference-count":15,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2019,2]]},"abstract":"<jats:p> In this paper, we show a polynomial-time algorithm for testing [Formula: see text]-planarity of embedded flat clustered graphs with at most two vertices per cluster on each face. <\/jats:p><jats:p> Our result is based on a reduction to the planar set of spanning trees in topological multigraphs (pssttm) problem, which is defined as follows. Given a (non-planar) topological multigraph [Formula: see text] with [Formula: see text] connected components [Formula: see text], do spanning trees of [Formula: see text] exist such that no two edges in any two spanning trees cross? Kratochv\u00edl et al. [SIAM Journal on Discrete Mathematics, 4(2): 223\u2013244, 1991] proved that the problem is NP-hard even if [Formula: see text]; on the other hand, Di Battista and Frati presented a linear-time algorithm to solve the pssttm problem for the case in which [Formula: see text] is a [Formula: see text]-planar topological multigraph [Journal of Graph Algorithms and Applications, 13(3): 349\u2013378, 2009]. <\/jats:p><jats:p> For any embedded flat clustered graph [Formula: see text], an instance [Formula: see text] of the pssttm problem can be constructed in polynomial time such that [Formula: see text] is [Formula: see text]-planar if and only if [Formula: see text] admits a solution. We show that, if [Formula: see text] has at most two vertices per cluster on each face, then it can be tested in polynomial time whether the corresponding instance [Formula: see text] of the pssttm problem is positive or negative. Our strategy for solving the pssttm problem on [Formula: see text] is to repeatedly perform a sequence of tests, which might let us conclude that [Formula: see text] is a negative instance, and simplifications, which might let us simplify [Formula: see text] by removing or contracting some edges. Most of these tests and simplifications are performed \u201clocally\u201d, by looking at the crossings involving a single edge or face of a connected component [Formula: see text] of [Formula: see text]; however, some tests and simplifications have to consider certain global structures in [Formula: see text], which we call [Formula: see text]-donuts. If no test concludes that [Formula: see text] is a negative instance of the pssttm problem, then the simplifications eventually transform [Formula: see text] into an equivalent [Formula: see text]-planar topological multigraph on which we can apply the cited linear-time algorithm by Di Battista and Frati. <\/jats:p>","DOI":"10.1142\/s0129054119500011","type":"journal-article","created":{"date-parts":[[2019,3,12]],"date-time":"2019-03-12T23:51:51Z","timestamp":1552434711000},"page":"197-230","source":"Crossref","is-referenced-by-count":3,"title":["Advances on Testing C-Planarity of Embedded Flat Clustered Graphs"],"prefix":"10.1142","volume":"30","author":[{"given":"Markus","family":"Chimani","sequence":"first","affiliation":[{"name":"Department of Mathematics\/Computer Science, University Osnabr\u00fcck, Wachsbleiche 27, Osnabr\u00fcck 49090, Germany"}]},{"given":"Giuseppe","family":"Di Battista","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria, Roma Tre University, Via della Vasca Navale 79, Rome, 00199, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5987-8713","authenticated-orcid":false,"given":"Fabrizio","family":"Frati","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria, Roma Tre University, Via della Vasca Navale 79, Rome, 00199, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8345-5806","authenticated-orcid":false,"given":"Karsten","family":"Klein","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science, Universit\u00e4t Konstanz, Box 76, Konstanz 78457, Germany"},{"name":"Monash University, Melbourne, Australia"}]}],"member":"219","published-online":{"date-parts":[[2019,3,12]]},"reference":[{"key":"S0129054119500011BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2014.08.001"},{"key":"S0129054119500011BIB002","doi-asserted-by":"publisher","DOI":"10.1145\/2629341"},{"key":"S0129054119500011BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/BF01188716"},{"key":"S0129054119500011BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.10.011"},{"key":"S0129054119500011BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2005.06.002"},{"key":"S0129054119500011BIB009","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00165"},{"key":"S0129054119500011BIB010","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00115"},{"key":"S0129054119500011BIB012","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00191"},{"key":"S0129054119500011BIB013","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00167"},{"key":"S0129054119500011BIB015","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794277123"},{"key":"S0129054119500011BIB020","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00192"},{"key":"S0129054119500011BIB021","doi-asserted-by":"publisher","DOI":"10.1137\/0404022"},{"key":"S0129054119500011BIB022","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00298"},{"key":"S0129054119500011BIB023","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2007.05.001"},{"key":"S0129054119500011BIB024","doi-asserted-by":"publisher","DOI":"10.1137\/0216030"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054119500011","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T15:40:16Z","timestamp":1565106016000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054119500011"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2]]},"references-count":15,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2019,3,12]]},"published-print":{"date-parts":[[2019,2]]}},"alternative-id":["10.1142\/S0129054119500011"],"URL":"https:\/\/doi.org\/10.1142\/s0129054119500011","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2019,2]]}}}