Avoidable overlapping curves in flow-chart

[LLyaudet]

Description

Hello, the graph drawing algorithm generates overlapping curves for some flow-chart, whilst some of these could be avoided.

Steps to reproduce

Look at this example diagram on a very big screen (sorry that's an example I made at work and that I anonymized) :

flowchart TD
    Z["`Aaa aaaaaaa :
    Aaaa aaaaaa Aaa aaaaaaaaa`"]
    Z -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA1| A
    Z -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA2| A
    A["`AAAAAAAAAAAAA :
    AAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA`"] -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA3| B["`AAAAAAAA :
    AAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA`"]
    A -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA4| B
    B -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA5| C["`AAAAAAAAAAAAAAAAAAAAAA :
    AAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA`"]
    B -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA6| D["`AAAAAAAAAAAAAAAAAA :
    AAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA`"]
    C -->|AAAAAAAAAAAAAAAAAA7| D
    D -->|AAAAAAAAAAAAAAAAAA8| E["`AAAAAAAAAAAAAAAAAAAAAAAAA`"]
    B -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA9| A
    C -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA10| A
    D -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA11| A
    B -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA12| B
    C -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA13| B
    D -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA14| B
    B -->|AAAAAAAAAAAAAAAAAAA15| B
    C -->|AAAAAAAAAAAAAAAAAAA16| B
    D -->|AAAAAAAAAAAAAAAAAAA17| B
    C -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA18| C
    D -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA19| C
    C -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA20| D
    D -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA21| D

Clearly arcs 12, 15, 9, 10, 11 could be drawn without crossing if wanted.

Screenshots

No response

Code Sample

flowchart TD
    Z["`Aaa aaaaaaa :
    Aaaa aaaaaa Aaa aaaaaaaaa`"]
    Z -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA1| A
    Z -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA2| A
    A["`AAAAAAAAAAAAA :
    AAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA`"] -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA3| B["`AAAAAAAA :
    AAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA`"]
    A -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA4| B
    B -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA5| C["`AAAAAAAAAAAAAAAAAAAAAA :
    AAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA`"]
    B -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA6| D["`AAAAAAAAAAAAAAAAAA :
    AAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
    AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA`"]
    C -->|AAAAAAAAAAAAAAAAAA7| D
    D -->|AAAAAAAAAAAAAAAAAA8| E["`AAAAAAAAAAAAAAAAAAAAAAAAA`"]
    B -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA9| A
    C -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA10| A
    D -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA11| A
    B -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA12| B
    C -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA13| B
    D -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA14| B
    B -->|AAAAAAAAAAAAAAAAAAA15| B
    C -->|AAAAAAAAAAAAAAAAAAA16| B
    D -->|AAAAAAAAAAAAAAAAAAA17| B
    C -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA18| C
    D -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA19| C
    C -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA20| D
    D -->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA21| D

Setup

• Mermaid version: latest Pycharm and GitHub
• Browser and Version: [Chrome, Edge, Firefox] : Firefox

Suggested Solutions

I saw a talk today by one of the authors of this article : https://arxiv.org/abs/2311.00437 From a point of view of graph algorithms, this problem as a decision problem is solved in time quasi-linear on any orientable surface. The result for planar graphs was known since 2017 apparently (see in the bibliography of the arXiv preprint this reference : Hsien-Chih Chang and Jeff Erickson. Untangling planar curves. Discrete & Computational Geometry, 58(4):889–920, 2017.) As of now it is a theoretical algorithm at least for surfaces with genus bigger than zero (non planar). I asked about the difficulty of implementing it, but the talker did not know how hard it would be to have an efficient and maintainable implementation in js. Note that the drawing could be improved iteratively with additional code in the flow-chart definition since it handles points on the surface that the curves are not allowed to pass through with continuous deformation on the surface.

Additional Context

No response

[LLyaudet]

If someone ever fancy to draw flow-charts on higher genus surfaces it would also help greatly. "Mermaid.js in 3D with torus/doughnut now live!" :)

[LLyaudet]

Hello :) No answer yet. I was wondering what is the algorithm used for planar drawing actually in mermaid.js. As you can see my example does not have a K5 or K{3,3} minor. But the drawing fails even on loops which no serious mathematician would consider in the beginning XD. Maybe you could try just a simple planar graph embedding algorithm first before. I found this recent article : https://arxiv.org/abs/1610.00130 But you would have to add a step of post-processing to fix the actual distances and positions. If the problem on my example comes from the size of the labels, it could be solved by enlarging all the graph without enlarging the text and/or by shifting a little some text above another one (shifting is not required but would probably be more space efficient than enlarging everything. I have looked at this also : https://en.wikipedia.org/wiki/Force-directed_graph_drawing But I know better the theory of graphs than the drawing of graphs. I think it could handle the big labels in the middle of the arcs by splitting each arc in 2 and making its label a temporary vertex with a bounding box. And then a postprocessing step could redraw both parts of the original arc to make it a single curve with control points that fix its origin and source and the fact that it passes at the center of the label or at one extremity if you prefer. It could be a choice given in the flow chart definition like :

• A -X||->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA4| B,
• A -|X|->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA4| B,
• A -||X->|AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA4| B, To put the crossing point where you want and fine tune your graph drawing. The suggested solution I gave first about Untangling planar curves could be used on top to draw non-planar graphs or if the main algorithm does not give a correct planar embedding when possible, as a "try harder" directive on named or enumerated arcs like untangle A --> B:1, A --> C:2 would try to untangle the first arc from A to B and the second arc from A to C in the flowchart definition.