A tree is one of the most fundamental structures of networks and has good properties on layouts, while it is weak from a fault-tolerant point of view. Motivated by these points of view, we consider an augmentation problem for a tree to increase fault-tolerance while preserving its good geometric property. A k-arbor-connected graph is defined to be a graph which has k spanning trees such that for any two vertices, the k paths between them in the spanning trees are pairwise edge-disjoint and internally vertex-disjoint. A k-arbor-connected graph has the abilities to execute fault-tolerant broadcastings and protection routings as a communication network. A book-embedding of a graph consists of a placement of its vertices on a line (called the spine) and an assignment of its edges to half planes (called pages) sharing the spine as a common boundary so that no two edges assigned to the same page cross. The pagenumber of a graph is the minimum number of pages required for a book-embedding of the graph. Book-embeddings have applications in fault-tolerant VLSI design, graph drawing, and other areas and they have widely been studied so far. We show that for any tree T of order n and for any k at most the radius of T, by adding new edges to T, a minimally k-arbor-connected graph T* with pagenumber k can be obtained in O(kn) time. Since any k-arbor-connected graph cannot be embedded in k-1 pages, T* is optimal with respect to not only the number of edges added to T but also the number of pages required for a book-embedding. Besides, we show that for k = 2 (respectively, 3) and for any tree T of order at least 4 (respectively, 6), a minimally k-arbor-connected graph with pagenumber k which contains T as a subgraph can be obtained in linear time. We moreover extend our result for a tree to a cactus for k greater than half of the maximum length of a cycle in the cactus, and to a unicyclic graph for any k at most the radius of the graph.

https://link.springer.com/chapter/10.1007/978-3-030-79987-8_25