User Guide: Grapher

0. Work Log

Excpected working:

1. Fully editing the graph - moving the vertices, drawing edges, everything

2. editing the graph in crossing-free mode - it should be impossible to make a crossing.

3. entering matchings mode if the graph is a perfect matching

   • click on an edge, all edges with which a flip could be performed are now red, and the clicked edge is green
   • click on one of the red edges, all other edges go back to black, and green lines are drawn for where the new lines would be drawn
   • click on one of the green lines, the flip is perfromed
   • the flip can be undone and re-done via history (ctrl+z or button)
   • in the matcings mode, only flips can be undone/redone

4. entering reconfiguration mode if the graph is a geometric triangulation, cfst or cfsp

   • click on an edge
     • if no valid flip with it can be performed, a notification should appear informing the user of this
     • otherwise, if it's a flippable edge, the flip should get indicated (or insta-flipped)
   • click on a vertex
     • see available vertexes that can be used for a new edge that would be valid flips highlighed as yellow
     • click on one, the one of the green edges should be clicked to confirm (or insta-flipped)

5. highlighting of colinear points

   • it's a toggle, so it needs to be turned off again in the settings. It obstructs visibility for flipping

6. settings

   • adjusting the hover/click proximity, colors, and by what factor the coordinates get multiplied
   • adjusting the size of the vertices and edges in pixels (slider)

7. coordinate multiplaction

   • it's at the bottom of the top part of the toolbar (icon is like small markers pointing diagonally)

8. re-zoom graph so that it's fully within the canvas

9. insta-flip toggle for perfect matchings and triangulations

   • insta-flip toggle is at the very bottom of the settings view

10. keyboard shortcuts: P for paths, T for trees, G for geometric triangulations, and M for matchings. R tries all of the reconfiguration types in that order, and enters the first one that fits the current graph. E for edit mode

Expected not working:

1. almost-perfect matchings
2. show all possible flips button/toggle
3. insta-flip toggle for almost-perfect matching

Note: Spiral graph with only 3 possible flips for matchings (with 3 'levels') can be found in data/matchings_only_3_flips_spiral_graph.txt

1. Introduction

1.1 Purpose: This is Grapher, an interactive web-app for investigating graph reconfigurations! The primary motivation for this tool is to help us explore graph reconfigurations for a few main types of geometric graphs.

• Configurations are plane drawings of straight line graphs with labeled vertices
• A reconfiguration step, or a flip, is an exchange of (a bounded number of) edges

1.2 Supported Graph Types for reconfiguration:

• Perfect Pairings / Matchings
• Almost-Perfect Pairings / Matchings
• Crossing-Free Spanning Trees
• Crossing-Free Spanning Paths
• Geometric Triangulations

1.3 Target Audience: Researchers, students, and anyone interested in exploring the structural properties and transformations of these specific graph classes.

2. Getting Started

2.1 Accessing the Tool:

An instance of the tool is hosted on GitHub pages.

The source code can also be found on Github. After cloning the repository, using the tool is as simple as opening the index.html file in the 'root' directory. Alternatively, the Live Server extension for VSCode can be used to speed up development (by default, it makes the tool accessible through localhost).

2.1 Requirements:

• A mouse or touchpad
• A modern web browser

3. Interface Overview

The tool interface is divided into several key areas:

• 3.1. Graph Area (Canvas):
  • The central panel where the graph is visually displayed.
  • All direct graph manipulations (adding/moving nodes, adding/removing edges) happen here.
  • Uses a grid background for reference.
• 3.2. Canvas toolbars :
  • Contain buttons to switch between interaction modes or perform global actions.
  • Main interactables:
    • [Graph] - Allows the user to switch between 'usage modes' - These include reconfigurations of each specific graph type, as well as unrestricted editing and crossing-free editing.
    • [Settings] - Shows a modal that allows configuring the app to the user's liking. Settings are saved in the browser's localStorage.
    • [Undo/Redo] - Allows moving through the history of changes to the current graph.
    • Resize - Sets up the display so that the current graph takes up the entire canvas area.
    • Expand - Multiplies the coordinates of all vertices by a set factor, only available in edit mode. (e.g. [-1, 4] becomes [-2, 8])
    • Show flips - Draws all possible flips on the current graph, only available in reconfiguration mode.
• 3.3. Right Sidebar:
  • 3.3.1. Change History:
    • Displays a chronological list of actions performed (e.g., "Add vertex", "Import file", "Add edge").
    • Allows navigation through the history using Undo/Redo, as well as jumping to any of the states in the history/undone sections.
    • Each entry in the history section stores the state of the graph that occurs after the change that it's describing is applied (indicated by the highlight line appearing under the list item)
    • Dynamically updates as you modify the graph.
  • 3.3.2. File Contents:
    • Shows a live representation of the current graph state in the supported file format.
    • Displays Vertex count and Edge count.
    • Lists vertex coordinates.
    • Lists edge connections (using 1-based indexing).
    • Hovering over vertices and edges will highlight them, cliking on a line will select them
    • Double-clicking on a line will allow the user to edit it (changing the coordinates of a vertex i.e. which vertices an edge connects)
    • Buttons:
      • Clear: Removes the current graph.
      • [Download Icon]: Downloads the current graph as a text file in the supported format.
      • [Copy Icon]: Copies the current graph data (in the supported format) to the clipboard.
• 3.4. Status Messages:
  • Appear in the bottom-left corner of the screen.
  • Provide feedback on actions or system status.
  • Blue Messages: Informational (e.g., "File imported successfully").
  • Red Messages: Indicate errors or problems (e.g., "Graph is not a valid Spanning Tree", "Invalid file format").
  • Messages disappear automatically after a few seconds.

4. Basic Workflow: Creating & Editing Graphs

You can start with a graph in two ways:

• 4.1. Importing a Graph:

  • Use the file selector button or drag and drop a valid graph file onto the indicated box.

* The tool only supports a specific plain text format (see [Section 6](#6-file-handling)). * ### 4.2. Building a Graph from Scratch (Edit Mode): * Ensure you are in 'Edit Mode' (See [Toolbar-modes](#8-toolbar-actions) and [Graph types](#12-supported-graph-types-for-reconfiguration)) * **Selecting Elements:** * Left-click a vertex or an edge to select it. Selected elements are rendered in a blue color. * Selection is used for actions like deleting or starting edge creation. * **Adding Vertices:** * Right-click on an empty space in the Graph Area, then select 'Add vertex'. A new vertex will appear at that location. * If a vertex is already selected, you also have the option to 'Add vertex and draw edge'. This allows quickly drawing paths. * **Adding Edges:** 1. Left-click on the first vertex (it should become selected - rendered in a blue color). 2. Right-click on the second vertex. 3. Select "Draw edge to here" from the context menu. * **Moving Vertices:** * Click and drag a vertex to a new position. The mouse pointer will change to a 'grab' or 'grabbing' hand icon. * The vertex will snap to the nearest coordinate once you let go. * **Removing Vertices:** 1. Right-click on the vertex you want to remove. 2. Select "Remove vertex" from the context menu. * *Note:* This will also automatically remove all edges connected to that vertex. * **Removing Edges:** 1. Right-click on the edge you want to remove. 2. Select "Remove edge" from the context menu. * **Deselecting:** Press the `Escape` key or click on empty space to clear any current selection. * **Panning/Zooming:** 1. To pan, simply use the mouse to drag the canvas. Grab anywhere except a vertex, the mouse pointer will change to a 'move' icon. 2. To zoom, use the use the scroll wheel. The tool will always zoom towards where the mouse is positioned. The vertices will always be rendered the same size, allowing you to have an easier time adjusting graphs where vertices are close to each other.

5. Performing Reconfigurations

This is the core feature for exploring graph transformations while maintaining specific structural properties.

• 5.1. Pre-requisite: Valid Graph: Ensure the graph currently displayed in the canvas conforms to the desired graph type (e.g., is a valid Crossing-Free Spanning Tree) before attempting reconfiguration for that type.
• 5.2. Select Graph Type: Choose the graph type you want to work with (toolbar, graph-mode icon, then click on the desired type). The tool will verify if the current graph matches the selected type. If not, an error message will appear. Note: You can also use keyboard shortcuts to enter these modes.
• 5.3. Initiate reconfigurations: The method depends on the selected graph type:

  • For Perfect Matchings

    • Edge-first Select one existing edge. The tool will highlight existing edges that could potentially be flipped together the selected one while maintaining the graph type. When a second edge is picked, the tool will highlight possible new edges that could be created between the vertices of these 2 old edges. Click one of the new edges to confirm.

    • Vertex-first Select one existing vertex. The tool will highlight existing vertices that could potentially be connected to the selected one, with the complements of each of these 2 also getting connected.

  • For All Other Graph Types:

    • Edge-first: Select one existing edge. The tool will highlight possible new edges which could be created, so that the graph type is preserved. Click one of these to confirm and perform the flip.

    • Vertex-first: Select two vertices that do not currently have an edge between them (representing a candidate edge). After selecting the first one, possible candidates for the second one will be highlighted. The tool will then highlight existing edges that could be removed if this candidate edge were added, maintaining the graph type.

• 5.4. Instant-flip: If the setting is enabled, and the state of the app is such that only 1 flip is possible with a selected edge (i.e. only 1 new edge is possible which preserves the graph type), or with a selected vertex pair (i.e. only 1 existing edge is removable while preserving the graph type), then the app will immediately perform this flip without waiting for user confirmation.

6. File Handling

• 6.1. Supported File Format:

  • Plain text file. (.txt usually, but extensions are ignored)
  • Line 1: Contains two integers: number_of_vertices number_of_edges.
  • Lines 2 to number_of_vertices + 1: Each line contains the x y coordinates for a vertex.
  • Following number_of_edges lines: Each line contains two integers u v, representing the 1-based indices of the vertices connected by an edge.
    • Note: In each line, the numbers can be separated by whitespace, comma, or semicolon (JS-regex: /\s|,|;/)

  Example:

  4 3
  0 0
  10 0
  10 10
  0 10
  1,2
  2;3
  3       4
  

  (This represents a square with 4 vertices and 3 edges connecting V1-V2, V2-V3, V3-V4)

• 6.2. Importing: Use the file input or drag-and-drop (See Section 4.1). Invalid formats will trigger an error message.

• 6.3. Exporting/Viewing: Use the 'File Contents' panel in the right sidebar to view the current graph data, download it as a .txt file, or copy it to the clipboard.

• 6.4. Your Data Grapher runs entirely in your web browser. Any data you import or otherwise input will not be sent to any server, and no cookies are used.

  • Note: The most recent graph is saved to Local Storage as a best-effort means of combatting data loss.

7. Change History & Undo/Redo

• The "Change History" panel lists all modifications made during the session.
• Use standard keyboard shortcuts to navigate history:
  • Ctrl+Z (Windows/Linux) or Cmd+Z (Mac): Undo the last action.
  • Ctrl+Shift+Z (Windows/Linux) or Cmd+Shift+Z (Mac): Redo the last undone action.
• Clicking on history list entries jumps to the state of the graph that ensues after the described change was applied.

8. Toolbar actions

The toolbar contains buttons that permit interacting with the program. The main usage is outlined here:

• Undo/Redo button go through History
• Resize canvas coordinates will adjust the zoom and move the view so that the entire current graph appears on the screen
• Explode coordinates will multiply every vertex' coordinates by a fixed amount (by default, 4). This is useful in case the current graph gets too cluttered.
• Change target graph type opens a modal with which the program can be adjusted for specific graph types.
  • Standard editing is described in Building a graph
  • Non-crossing editing is the same, with the additional rule that crossings can't be created
  • The other modes are flip modes, listed under Supported graph types, and described under Performing reconfigurations

9. Keyboard Shortcuts

• Undo: Ctrl+Z / Cmd+Z
• Redo: Ctrl+Shift+Z / Cmd+Shift+Z
• Delete Selected: Delete or Backspace (when a vertex or edge is selected in Edit Mode).
• Deselect: Escape
• Clear the file Ctrl+K
• Mode switching
  • R for entering whichever mode is applicable to the current graph type (if any) - so, if the graph is a matching, it will enter matchings mode, and if it's a triangulation, it will enter triangulation mode, etc. Note: Paths will be attempted before trees, because all paths are also trees.
  • E for entering EDIT mode
  • G for entering Triangulation mode if possible
  • P for entering Paths mode if possible
  • T for entering Trees mode if possible
  • M for entering Matchings mode if possible

10. Settings

The settings button in the toolbar shows a modal that allows configuring the app to the user's liking. The most important settings appear at the top. This is where the user can turn on or off the displaying of edge intersections, colinear triples of vertices, and the 'instant-flip' feature for reconfuigurations, which will immediately perform a flip as soon as it is unambiguous. The display sizes of certain items are also configurable.

There are other configurable settings, such as the color of displayed items:

11. Troubleshooting / FAQ

• Q: Why can't I import my file?
  • A: Check if it strictly follows the format described in Section 6.1. Ensure vertex indices for edges are 1-based, not 0-based. Verify the vertex and edge counts on the first line match the actual data.
• Q: Why does the tool say my graph isn't a valid [Graph Type] when trying reconfiguration?
  • A: Ensure your graph strictly meets the definition of the selected type (e.g., a spanning tree must connect all vertices with no cycles, a perfect matching must cover all vertices exactly once, geometry constraints like non-crossing might apply). Correct the graph in Edit Mode first. Worst case, a more useful error message might be logged in the browser console (usually accessed via F12)