Der linke + rechte Part ergeben zusammen die Anzahl der Crossings. Wir machen da eine Umfornung: Die Anzahl der Crossings ist: [Summe über c_ij x_ij + c_ji x_ji]. Wegen x_ji = 1 - x_ij folgt: [Summe über [c_ij x_ij + c_ji (1 - x_ij)] = [Summe über c_ij x_ij + c_ji - c_ji x_ji] = [Summe über (c_ij - c_ji) x_ij + c_ji] = [Summe über (c_ij - c_ji) x_ij] + [Summe über c_ji]. Der rechte Teil [Summe über c_ji] ist konstant, also zählen wir im ILP nur den linken Teil. Um dann am Ende die exakte Anzahl der Kreuzungen zu bekommen, muss man noch [Summe über c_ji] draufaddieren. Alternativ kann man [Summe über c_ji] auch vorberechnen und in der Zielfunktion des ILPs draufaddieren.

You're right, thank you!

No, this step is much simpler (and thus not optimal): similar to the crossing minimization, you just go through the layers bottom-up, then top-down, and so on. For each layer, you look at the dummy vertices and see if you can move them to remove bends. You do that until there are no more local improvements you can do.

Bei dem Beispiel bin ich schon in der Mitte eingestiegen, also bei j=5. Ich bin davon ausgegangen, dass wir j=2,3,4 schon erledigt haben.

It definitely is! Here are a few links that might help you: gist.github.com/rmukh/cbfee78cbfbe73a36638a409726b7a84 codeforces.com/blog/entry/81768 github.com/leomccormack/convhull_3d

Thank you! For this part, I've been following (with some modifications) chapter 4 "Drawing on Physical Analogies" by Ulrik Brandes in the book "Drawing Graphs: Methods and Models" edited by Michael Kaufmann and Dorothea Wagner: link.springer.com/chapter/10.1007/3-540-44969-8_4

Hey, that's interesting! Which graph and which parameters did you use? I tried my test graphs with both l^2 and distance^2, but both variants gave me almost the same drawing. In every source I can find, including the original paper, they square l and not the distance in the repulsive force. This is from the original paper, where their k is our l and their x is the distance between u and v: function f_a(x) := begin return x^2/k end; function f_r(x) := begin return k^2/x end; See, e.g., onlinelibrary.wiley.com/doi/epdf/10.1002/spe.4380211102 cs.brown.edu/people/rtamassi/gdhandbook/chapters/force-directed.pdf arxiv.org/pdf/1201.3011.pdf algo.uni-trier.de/demos/forceDirected.html / algo.uni-trier.de/demos/script/algorithm/fruchtermanReingoldAlgorithm.js

did you take mod(distance) or just distance ?

@@sayanbaidya9724 I'm not sure what you mean by mod(distance). Do you mean abs(distance)? distance should always be positive. I calculate sqrt( (v.x - u.x)^2 + (v.y - u.y)^2 ).

@@PhilippKindermann Hi I was asking the original person who commented whether he took mod or not as results come same if I take mod(distance) or distance ^2. Yes you are right, it should always be positive value.

Hey, the bounding triangle is crucial so that we can plug subdrawings together at the P- and S-nodes. Without them, we don't know how the drawings look like and how to combine them. This is a common approach when you have an inductive or recursive algorithm that follows some graph decomposition.

Danke! Wenn ich etwas Zeit hab, pack ich bestimmt auch mal Timestamps dazu... ^^'

For simple layouts there are many options, for example: Javascript: - d3.force: d3js.org/ - sigma.js: www.sigmajs.org/ - vis.js: visjs.github.io/vis-network/examples/ - dracula: github.com/strathausen/dracula Python: - networkx: networkx.org/ - Pyvis: pyvis.readthedocs.io/en/latest/index.html - Jaal: github.com/imohitmayank/jaal - ogdf-python: github.com/ogdf/ogdf-python Java (wouldn't recommend it): - JGraphX: github.com/jgraph/jgraphx C/C++: - OGDF: github.com/ogdf/ogdf/ - LEDA: www.algorithmic-solutions.info/leda_guide/GraphWin.html I'm aware of 2 GPU-based solutions, but haven't really tried them out yet. - cugraph: github.com/rapidsai/cugraph/blob/main/notebooks/algorithms/layout/Force-Atlas2.ipynb - GraphWaGu: www.willusher.io/publications/graphwagu I think that the two most powerful library are the open-source OGDF(ogdf.uos.de/), available for C++ and Python, and the commercial yFiles (www.yworks.com/products/yfiles), available for JavaScript, Java, and C#.

Hey! I created the slides with ipe and I'm showing the ipe editor window, so I can edit everything on the fly: ipe.otfried.org/ You can download the slides from algo.uni-trier.de/lectures/graphvis and directly open them in Ipe

Thanks for sharing the tool and slides, Philipp! It's a very nice tool.@@PhilippKindermann

I used Ipe (ipe.otfried.org/) to create the slides and Camtasia (www.techsmith.com/video-editor.html) to record and edit the video.

@@PhilippKindermann big thank sir i do the same course for master 1 in my country and your courses are for me a big support

There's algorithms for Line Voronoi Diagrams (Voronoi Diagrams of Line Segments). See for example this paper: people.mpi-inf.mpg.de/~mehlhorn/ftp/VoronoiLineSegments.pdf There's an implementation for ArcGIS: github.com/UNTGeography/VoronoiDiagramsGIS It's implemented in the Boost C++ Library: www.boost.org/doc/libs/1_75_0/libs/polygon/doc/voronoi_main.htm And there are wrappers for Python: github.com/fabanc/pyvoronoi and for C#: github.com/fabanc/SharpBoostVoronoi

Thank you! You can find the slides here: algo.uni-trier.de/lectures/algeo/slides/

The O((n + I) log n) = O(n log n) running time is to intersect two convex regions. But we have n convex regions (half planes) that we have to intersect. We do that via divide-and-conquer (like MergeSort), which adds an additional log n factor.

@@PhilippKindermann Thanks a lot, I have been searching for an explanation for about an hour. Thanks a lot, I wish the textbook had a worked out an example tho... ):

Hey, I use the vector drawing program ipe: ipe.otfried.org/ You can also open all my slides with the program

@@PhilippKindermann Thank you.

The reason I didn't use a MaxHeap is that deletion cannot be done trivially in logarithmic time. Otherwise a MaxHeap would be easier, that's true.

You only remove the cycles such that a hierarchical drawing exists. But if you want to display the original graph at the end, you have to revert these changes.

Many state diagrams are series-parallel, but in general they don't have to be.