Groups keyboard shortcuts have been updated
Dismiss
See shortcuts
PlanarDrawLayout for biconnected graphs
14 views
Skip to first unread message
Małgorzata Nowicka
Nov 23, 2021, 2:31:29 AM11/23/21
to ogdf
Hello!
In the documentation for the PlanarDrawLayout Class, the referenced paper (M. Chrobak, G. Kant: Convex Grid Drawings of 3-connected Planar Graphs. International Journal of Computational Geometry and Applications 7(3), pp. 211-223, 1997.) concerns the 3-connected graphs. However, the PlanarAugmentation Class used for achieving the desired connectivity is ensuring only the biconnectivity of the input graph. I would appreciate your help with understanding this aspect of the algorithm!
Best regards,
Malgorzata Nowicka
Dagobert Smart
Dec 1, 2021, 8:42:26 AM12/1/21
to ogdf
Dear Małgorzata,
please take this with a grain of salt as I have only limited knowledge of the topic and have not read the paper very thoroughly. However, I assume it works as follows:
The proof of the algorithm's correctness does not directly depend on the triconnectedness of the graph. Rather, the triconnectedness is only needed to ensure that a canonical ordering (an ordered partition of the vertices with certain properties) exists.
In other papers, the notion of a canonical ordering was generalized to biconnected (not necessarily triconnected) graphs, see e.g.
Definition 3.2 of Harel, David, and Meir Sardas. "An algorithm for straight-line drawing of planar graphs." Algorithmica 20.2 (1998): 119-135.
This notion of a canonical ordering still fulfills the properties that are needed to ensure the correctness of the algorithm by Chrobak & Kant. However, it does not require the graph to be triconnected.
Hence, it suffices to augment the graph to a biconnected graph (PlanarAugmentation) and compute a canonical ordering for biconnected graphs (BiconnectedShellingOrder).
Best regards,
Dagobert
please take this with a grain of salt as I have only limited knowledge of the topic and have not read the paper very thoroughly. However, I assume it works as follows:
The proof of the algorithm's correctness does not directly depend on the triconnectedness of the graph. Rather, the triconnectedness is only needed to ensure that a canonical ordering (an ordered partition of the vertices with certain properties) exists.
In other papers, the notion of a canonical ordering was generalized to biconnected (not necessarily triconnected) graphs, see e.g.
Definition 3.2 of Harel, David, and Meir Sardas. "An algorithm for straight-line drawing of planar graphs." Algorithmica 20.2 (1998): 119-135.
This notion of a canonical ordering still fulfills the properties that are needed to ensure the correctness of the algorithm by Chrobak & Kant. However, it does not require the graph to be triconnected.
Hence, it suffices to augment the graph to a biconnected graph (PlanarAugmentation) and compute a canonical ordering for biconnected graphs (BiconnectedShellingOrder).
Best regards,
Dagobert
Małgorzata Nowicka
Dec 3, 2021, 2:36:48 AM12/3/21
to ogdf
I understand now, thank you for your help!
Best regards,
Malgorzata Nowicka
Reply all
Reply to author
Forward
0 new messages