scientific article; zbMATH DE number 1979709

Publication date 14 September 2003

Distance in graphs (05C12) Structural characterization of families of graphs (05C75)

Let \(G\) be a finite simple planar graph with nonnegatively weighted vertices, edges, and faces and nonnegatively priced vertices and edges of its triangulization. By \(w(G)\), \(w_V(G)\), \(w_E(G)\), \(w_F(G)\) the weight of \(G\), its vertex set, edge set, face set are denoted, respectively. By \(c_E(G)\) and \(c(G)\) the cosets of edge path and full path are denoted. A set \(C\subset G\) is called a separator of \(G\) if \(G\) can be divided into three subsets \(A\), \(B\), and \(C\), such that there are no elements in the set \(A\) which are incident to some elements of \(B\) and there are no vertices in \(A\) adjoint to some vertices of \(B\). The main result of the paper is the theorem by R.~J.~Lipton, R.~E.~Tarjan, and the author which asserts that a planar triangular graph \(G\) with nonnegative weight function \(w=w_V+w_E+w_F\) and skeleton \(S\) possesses a cycle separator \(C\) such that all except one, denoted as \(e\), its edges are in \(S\), \(c(C)\leq c_{\max}+c_E(e)\) and \[ \min \{w(A),w(B)\} \geq \displaystyle \frac{w(G)}{3}- \frac{w(G)}{2}-\frac{-w_{\min}+\sum_{x=E_e} w_E(x)+2w_F(F_e)}{6}. \] Here \(w_{\min}\) is the minimal weight of vertices in \(C\), \(F_e\) is the face incident to the edge \(e\), \(E_e\) is the set of edges incident to the face \(F_e\). The face \(F_e\) lies in the heaviest of the subsets \(A\) and \(B\), if \(w(A)=w(B)\) then it lies in the subset with more faces. Some algorithms of the separator constructions and their applications for particular families of graphs are considered.

Recommendations

Cited in

(15)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4428085)