✦ LIBER ✦

The sizes of maximal planar, outerplanar, and bipartite planar subgraphs

✍ Scribed by Robert Cimikowski; Don Coppersmith

Book ID: 103060888
Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 307 KB
Volume: 149
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00326-e

No coin nor oath required. For personal study only.

✦ Synopsis

We define the subvariance Sj,(o~) of a family of graphs ~ with respect to property o~ to be the infimum of the ratio IH~ 1/11421, where HI and 1-12 are any two maximal spanning subgraphs of G with property ~, and where G is a member of ft. It is shown that, for the family of all i i connected graphs, the subvariance when ~ is planar, outerplanar, and bipartite planar, is 3, 2, and ½, respectively.

📜 SIMILAR VOLUMES

On the number of maximal bipartite subgr

On the number of maximal bipartite subgraphs of a graph

✍ Jesper Makholm Byskov; Bolette Ammitzbøll Madsen; Bjarke Skjernaa 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 72 KB 👁 2 views

We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105 n=10 % 1:5926 n ; such subgraphs show an upper bound of O(12 n=4 ) ¼ O(1:8613 n ) and give an algorithm that finds all maximal

On the connectivity of maximal planar gr

On the connectivity of maximal planar graphs

✍ S. L. Hakimi; E. F. Schmeichel 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 254 KB 👁 1 views

On the Planar Decomposition of a Complet

On the Planar Decomposition of a Complete Bipartite Graph

✍ Shirakawa, Isao; Takahashi, Hiromitsu; Ozaki, Hiroshi 📂 Article 📅 1968 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 713 KB

Spanning Planar Subgraphs of Graphs in t

Spanning Planar Subgraphs of Graphs in the Torus and Klein Bottle

✍ R. Brunet; M.N. Ellingham; Z.C. Gao; A. Metzlar; R.B. Richter 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 685 KB

There are two main purposes of this article. First we show that every 3-connected graph embedded in the torus or the Klein bottle has a spanning planar subgraph which is 2-connected, and in fact has a slightly stronger connectivity property. Second, this subgraph is applied to show that every 3-conn

On the existence and connectivity of a c

On the existence and connectivity of a class of maximal planar graphs

✍ S. Fanelli 📂 Article 📅 1982 🏛 Springer Milan 🌐 English ⚖ 352 KB

Light subgraphs in the family of 1-plana

Light subgraphs in the family of 1-planar graphs with high minimum degree

✍ Xin Zhang, Gui Zhen Liu, Jian Liang Wu 📂 Article 📅 2011 🏛 Institute of Mathematics, Chinese Academy of Scien 🌐 English ⚖ 260 KB