{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T04:27:47Z","timestamp":1778732867046,"version":"3.51.4"},"reference-count":18,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2020,8,13]],"date-time":"2020-08-13T00:00:00Z","timestamp":1597276800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This paper introduces and studies the following beyond-planarity problem, which we call h-Clique2Path Planarity. Let G be a simple topological graph whose vertices are partitioned into subsets of size at most h, each inducing a clique. h-Clique2Path Planarity asks whether it is possible to obtain a planar subgraph of G by removing edges from each clique so that the subgraph induced by each subset is a path. We investigate the complexity of this problem in relation to k-planarity. In particular, we prove that h-Clique2Path Planarity is NP-complete even when h=4 and G is a simple 3-plane graph, while it can be solved in linear time when G is a simple 1-plane graph, for any value of h. Our results contribute to the growing fields of hybrid planarity and of graph drawing beyond planarity.<\/jats:p>","DOI":"10.3390\/a13080194","type":"journal-article","created":{"date-parts":[[2020,8,13]],"date-time":"2020-08-13T09:23:44Z","timestamp":1597310624000},"page":"194","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Graph Planarity by Replacing Cliques with Paths"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7602-1524","authenticated-orcid":false,"given":"Patrizio","family":"Angelini","sequence":"first","affiliation":[{"name":"School of Computer Science, John Cabot University, 00165 Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Eades","sequence":"additional","affiliation":[{"name":"School of Computer Science, Faculty of Engineering, The University of Sydney, Sydney 2006, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seok-Hee","family":"Hong","sequence":"additional","affiliation":[{"name":"School of Computer Science, Faculty of Engineering, The University of Sydney, Sydney 2006, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karsten","family":"Klein","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Konstanz, 78464 Konstanz, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen","family":"Kobourov","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Arizona, Tucson, AZ 85721, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[{"name":"Department of Engineering, University of Perugia, 06123 Perugia, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8547-5934","authenticated-orcid":false,"given":"Alfredo","family":"Navarra","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Perugia, 06123 Perugia, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9192-2067","authenticated-orcid":false,"given":"Alessandra","family":"Tappini","sequence":"additional","affiliation":[{"name":"Department of Engineering, University of Perugia, 06123 Perugia, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,8,13]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1057\/palgrave.ivs.9500092","article-title":"On the readability of graphs using node-link and matrix-based representations: A controlled experiment and statistical analysis","volume":"4","author":"Ghoniem","year":"2005","journal-title":"Inf. Vis."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"2940","DOI":"10.1109\/TVCG.2018.2865940","article-title":"Node-Link or Adjacency Matrices: Old Question, New Insights","volume":"25","author":"Okoe","year":"2019","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1302","DOI":"10.1109\/TVCG.2007.70582","article-title":"NodeTrix: A Hybrid Visualization of Social Networks","volume":"13","author":"Henry","year":"2007","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"139","DOI":"10.7155\/jgaa.00461","article-title":"Computing NodeTrix Representations of Clustered Graphs","volume":"22","author":"Frati","year":"2018","journal-title":"J. Graph Algorithms Appl."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"3464","DOI":"10.1007\/s00453-019-00585-6","article-title":"NodeTrix Planarity Testing with Small Clusters","volume":"81","author":"Liotta","year":"2019","journal-title":"Algorithmica"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1109\/TVCG.2016.2598472","article-title":"Blockwise Human Brain Network Visual Comparison Using NodeTrix Representation","volume":"23","author":"Yang","year":"2017","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Angori, L., Didimo, W., Montecchiani, F., Pagliuca, D., and Tappini, A. (2019, January 17\u201320). ChordLink: A New Hybrid Visualization Model. Proceedings of the Graph Drawing and Network Visualization\u201427th International Symposium, GD, Prague, Czech Republic.","DOI":"10.1007\/978-3-030-35802-0_22"},{"key":"ref_8","unstructured":"Di Giacomo, E., Lenhart, W.J., Liotta, G., Randolph, T.W., and Tappini, A. (March, January 27). (k, p)-Planarity: A Relaxation of Hybrid Planarity. Proceedings of the WALCOM: Algorithms and Computation\u201413th International Conference, Guwahati, India."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"731","DOI":"10.7155\/jgaa.00437","article-title":"Intersection-Link Representations of Graphs","volume":"21","author":"Angelini","year":"2017","journal-title":"J. Graph Algorithms Appl."},{"key":"ref_10","first-page":"4:1","article-title":"A Survey on Graph Drawing Beyond Planarity","volume":"52","author":"Didimo","year":"2019","journal-title":"ACM Comput. Surv."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.cosrev.2017.06.002","article-title":"An annotated bibliography on 1-planarity","volume":"25","author":"Kobourov","year":"2017","journal-title":"Comput. Sci. Rev."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Angelini, P., Eades, P., Hong, S., Klein, K., Kobourov, S.G., Liotta, G., Navarra, A., and Tappini, A. (2018, January 26\u201328). Turning Cliques into Paths to Achieve Planarity. Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD), Barcelona, Spain.","DOI":"10.1007\/978-3-030-04414-5_5"},{"key":"ref_13","unstructured":"Bekos, M.A., Kaufmann, M., and Raftopoulou, C.N. (2017, January 4\u20137). On Optimal 2- and 3-Planar Graphs. Proceedings of the 33rd International Symposium on Computational Geometry, SoCG 2017, Brisbane, Australia."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/BF01215922","article-title":"Graphs Drawn with Few Crossings per Edge","volume":"17","author":"Pach","year":"1997","journal-title":"Combinatorica"},{"key":"ref_15","unstructured":"Kindermann, P., Klemz, B., Rutter, I., Schnider, P., and Schulz, A. (2018, January 21\u201323). The Partition Spanning Forest Problem. Proceedings of the 34th European Workshop on Computational Geometry (EuroCG\u201918), Franconia, Germany."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1346330.1346336","article-title":"Minimum-weight triangulation is NP-hard","volume":"55","author":"Mulzer","year":"2008","journal-title":"J. ACM"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Karp, R.M. (1972, January 20\u201322). Reducibility Among Combinatorial Problems. Proceedings of the symposium on the Complexity of Computer Computations, New York, NY, USA.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/s11634-010-0079-y","article-title":"Fast algorithms for determining (generalized) core groups in social networks","volume":"5","author":"Batagelj","year":"2011","journal-title":"Adv. Data Anal. Classif."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/8\/194\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:59:58Z","timestamp":1760176798000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/8\/194"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,13]]},"references-count":18,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2020,8]]}},"alternative-id":["a13080194"],"URL":"https:\/\/doi.org\/10.3390\/a13080194","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,13]]}}}