Small extension to Java Jung to work on embedded graphs. This contains an implementation for drawing graphs NIC-planar 1-bend RAC in quadratic area. This implementation is based on the article "Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends", which can be found at https://arxiv.org/abs/1806.10044 โ see also https://doi.org/10.1016/j.comgeo.2019.07.006 for the journal version.
Navigate to the top-level directory of this project (where the pom.xml is). Beside a sufficiently new Java version you need maven to be installed. Build via maven:
mvn package
Execute the sample main method:
mvn exec:java -Dexec.mainClass="de.uniwue.informatik.main.DrawGraphs"
This will open a window showing some stages of the algorithm for creating a NIC-planar drawing with right-angle crossings on a quadratic size grid of a sample NIC-planar graph. The stages are as follows (the next stage appears by pressing the "Step" button).
- The drawing is the one produced by the shift algorithm of Harel and Sardas, where the crossing edges have been removed and there is a divided kite for each crossing (containing dummy edges).
- The drawing of the previous stage scaled up by a facator of 2.
- The drawing after inserting the 1-bend edges that cross in a right angle inside the kites. There are three cases with one case appearing per kite (for a description see the article).
- The drawing after removing the dummy edges. This is the final NIC-planar 1-bend RAC drawing of the input sample graph.
For the displayed graph drawings, there is also an output as ipe files at:
target/drawings/
The source code is available. You may modify it to try different graphs and things.
For any question regarding this project send an email to: [email protected]