Record number :
Title of article :
On the Minimum Cut of Planarizations
Author/Authors :
C.M. Chimani، نويسنده , , Markus and Gutwenger، نويسنده , , Carsten and Mutzel، نويسنده , , Petra، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2007
Pages :
From page :
To page :
Abstract :
Every drawing of a non-planar graph G in the plane induces a planarization, i.e., a planar graph obtained by replacing edge crossings with dummy vertices. In this paper, we consider the relationship between the capacity of a minimum st-cut in a graph G and its crossing minimal planarizations. We show that these capacities need not be equal. On the other hand, we prove that every such planarization can be efficiently transformed into another crossing minimal planarization that preserves the capacity of a minimum st-cut in G. Furthermore, we extend the result to general (reasonable) planarizations.
Keywords :
minimum cut , Graph Planarization , crossing number
Journal title :
Electronic Notes in Discrete Mathematics
Serial Year :
Link To Document :