The Weighted Barycenter Drawing Recognition Problem
This study delves into the Weighted Barycenter Drawing Recognition Problem, focusing on characterizing force-directed layouts and computing weights for planar graph edges. With a background in the Weighted Barycenter Algorithm, the paper explores related work and presents results and conclusions from the research.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Graph Drawing and Network Visualization 2018, Barcelona The Weighted Barycenter Drawing Recognition Problem Peter Eades University of Sydney Patrick Healy, Nikola S. Nikolov University of Limerick
Our Work in a Nutshell Generic problem: Given drawing of graph ?, can we say that is a force-directed drawing of ?? Motivation: Characterisation of force-directed layouts Inspired by the need to classify bobbin lace drawings (thanks to Veronica Irvine, University of Victoria) Narrowing the scope: Given a straight-line planar drawing of a triconnected planar graph G, can we compute weights for the edges of ? so that is the weighted barycenter drawing of ?? of 16 GD2018 2
Outline 1. Related Work 2. Background 3. Problem Definition 4. Results 5. Conclusion of 16 GD2018 3
1. Related Work Characterisation of drawings that arise from the Schnyder s grid embedding algorithm (Bonichon et al., 2010). This drawing is taken from David Epstein s course Graph Algorithms https://www.ics.uci.edu/~eppstein/gina/schnyder/ of 16 GD2018 4
2. Background Weighted Barycenter Algorithm Input: triconnected planar graph ? = (?,?) with an edge weight function ? set of vertices ?0 ? convex polygon ?0 Output: straight-line drawing of ? with ?0 drawn as ?0 of 16 GD2018 5
2. Background Weighted Barycenter Algorithm The algorithm: Assign a position ?? to each internal vertex ? such that ?? is the weighted barycenter of the positions of its neighbours ?(?). 1 ??= ????? ?? ? ???? ? ? ? of 16 GD2018 6
2. Background Weighted Barycenter Algorithm The algorithm: Assign a position ?? to each internal vertex ? such that ?? is the weighted barycenter of the positions of its neighbours ?(?). Theorem 1. (Tutte [15, 16], Floater [8]) The drawing output by the weighted barycenter algorithm is planar, and each face is convex. of 16 GD2018 7
2. Background Weighted Barycenter Algorithm The algorithm: Assign a position ?? to each internal vertex ? such that ?? is the weighted barycenter of the positions of its neighbours ?(?). Weighted barycentre drawings of the same graph embedding with different weights. of 16 GD2018 8
2. Background Weighted Barycenter Algorithm Can be viewed as a force directed graph drawing method, as follows. We define the energy ? ?,? of an internal edge ?,? as ? ?,? =1 2=1 2+ ?? ?? 2 2???? ??,?? 2??? ?? ?? ??= ? ??,?? is the Euclidean distance between ??and ?? ??,?? of 16 GD2018 9
3. Problem Definition The Weighted Barycenter Drawing Recognition (WBDR) Problem Given a straight-line and convex planar drawing of a triconnected plane graph ?, do positive weights ??? for all internal edges (?,?) exist, such that is a weighted barycenter drawing? of 16 GD2018 10
4. Results The Model Replace each undirected edge (?,?) of ? with two directed edges (?,?) and (?,?). Let ?+(?) denote the out-neighbours of vertex ?. Since each face is convex, each internal vertex position is a convex linear combination of the vertex positions of its neighbours. ??= ????? ???= 1 and Note: The values of ??? can be determined in linear time. ? ?+? ? ?+? of 16 GD2018 11
4. Results The Model Replace each undirected edge (?,?) of ? with two directed edges (?,?) and (?,?). Problem: The weights ???can be viewed as barycentric weights (what we are looking for!), however, in general ??? ???. Solution: Scale each weight ???by a node-specific factor ??> 0, such that ?????= ?????. WBDR Problem Reduction: Do the scale-factor equations?????= ????? have a non- trivial solution for the variables ??? Note: it can be easily shown that the existence of a non-trivial solution implies positive ??. of 16 GD2018 12
4. Results The Main Theorem Theorem 2. The scale-factor equations ?????= ????? have a non-trivial solution iff for each strictly internal face ? = (?0,?1, ,?? 1,?? = ?0) in ?, the following facial-cycle equations are true ? 1 ? ???,??+1= ???,?? 1 ?=0 ?=1 Remark. The facial-cycles equations say that, for each strictly internal face, the clockwise product of the ???is equal to the anticlockwise product of the ???. of 16 GD2018 13
4. Results The Main Theorem Theorem 2. The scale-factor equations ?????= ????? have a non-trivial solution iff for each strictly internal face ? = (?0,?1, ,?? 1,?? = ?0) in ?, the following facial-cycle equations are true ? 1 ? ???,??+1= ???,?? 1 ?=0 ?=1 Sketch of the proof. (complete proof in the paper) Write the equations ?????= ????? as ?? = 0, where ? is the (? |?0|) ?weighted vertex- edge incidence matrix of the graph ?. There is a non-trivial solution for the vector ? if and only if ? has rank less than (? |?0|). Show that for any ?-cycle ?? in ?, the submatrix of ? corresponding to the edges of ?? has rank ? 1 if and only if the cycle equation above holds for ??. The result follows since the facial cycles form a cycle basis. 1. 2. 3. of 16 GD2018 14
4. Results Corollary 1. A drawing of a cubic graph is a weighted barycenter drawing if and only if the scale-factor equations ?????= ????? have rank smaller than ? |?0|. Corollary 2. For cubic graphs, there is a linear time algorithm for the weighted barycenter recognition problem. Corollary 3. Suppose that is a convex planar drawing of a Halin graph such that the internal edges form a tree. Then is a weighted barycenter drawing. Corollary 4. A plane convex drawing is a weighted barycenter drawing iff there are solutions ??? to the scale-factor equations ?????= ????? such that the facial-cycle equations hold for every internal face. Note: Although Corollary 4 is quite elegant, it does not lead to an immediately practical algorithm because the facial-cycle equations are not linear. of 16 GD2018 15
5. Conclusion First attempt to give algorithms to recognise the output of a particular force-directed method, namely the weighted barycenter method. We hope our results inspire further research in this direction. In particular, it would be interesting to know if the results of other force- directed methods can be automatically recognised. of 16 GD2018 16
