Efficient reassembling of three-regular planar graphs

Assaf Kfoury () and Laura Sisson ()
Additional contact information
Assaf Kfoury: Boston University
Laura Sisson: Boston University

Journal of Combinatorial Optimization, 2020, vol. 39, issue 4, No 10, 1153-1207

Abstract: Abstract A reassembling of a simple graph $$G = (V,E)$$ G = ( V , E ) is an abstraction of a problem arising in earlier studies of network analysis (Bestavros and Kfoury, in: Proceedings of IFIP working conference on domain-specific 1640 languages (DSL 2011), EPTCS volume 66, 2011; Kfoury, in: Proceedings of SBLP 2011: Brazilian symposium on programming; Kfoury, in Sci Comput Program 93(Part A):19–38; Soule et al., in: Proceedings of 4th international workshop on equation-based object oriented modeling languages and tools, Zürich). There are several equivalent definitions of graph reassembling; in this report we use a definition which makes it closest to the notion of graph carving. A reassembling is a rooted binary tree whose nodes are subsets of V and whose leaf nodes are singleton sets, with each of the latter containing a distinct vertex of G. The parent of two nodes in the reassembling is the union of the two children’s vertex sets. The root node of the reassembling is the full set V. The edge-boundary degree of a node in the reassembling is the number of edges in G that connect vertices in the node’s set to vertices not in the node’s set. A reassembling’s $$\alpha $$ α -measure is the largest edge-boundary degree of any node in the reassembling. A reassembling of G is $$\alpha $$ α -optimal if its $$\alpha $$ α -measure is the minimum among all $$\alpha $$ α -measures of G’s reassemblings. The problem of finding an $$\alpha $$ α -optimal reassembling of a simple graph in general was already shown to be NP-hard (Kfoury and Mirzaei, in J Comb Optim 33(3):1057–1089; Mirzaei and Kfoury, in: Efficient reassembling of graphs, Part 2: the balanced case. CoRR, arXiv:1602.02863 ; among others). In this report we present an algorithm which, given a 3-regular plane graph $$G = (V,E)$$ G = ( V , E ) as input, returns a reassembling of G with an $$\alpha $$ α -measure independent of $$n = |\,V\,|$$ n = | V | and upper-bounded by 2k, where k is the edge-outerplanarity of G. (Edge-outerplanarity is distinct but closely related to the usual notion of outerplanarity; as with outerplanarity, for a fixed edge-outerplanarity k, the number n of vertices can be arbitrarily large). Our algorithm runs in linear time $${{\mathcal {O}}}(n)$$ O ( n ) . Moreover, we construct a class of 3-regular plane graphs for which this $$\alpha $$ α -measure is optimal, by proving that 2k is the lower bound on the $$\alpha $$ α -measure of any reassembling of a graph in that class.

Keywords: Planar graphs; Three-regular graphs; Graph carving; Routing tree; Graph reassembling (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00555-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:39:y:2020:i:4:d:10.1007_s10878-020-00555-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00555-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().