Opened 2 years ago

Closed 21 months ago

# Drawing generalizations of generalized Petersen graphs

Reported by: Owned by: Nina Klobas Nina Klobas major sage-9.3 graph theory vipul73921 Nina Klobas David Coudert N/A 0d739ba

### comment:1 Changed 2 years ago by Nina Klobas

Branch: → u/gh-NinaKl/drawing_generalizations_of_generalized_petersen_graphs

### comment:2 Changed 2 years ago by Nina Klobas

Authors: → Nina Klobas → 7f3ef45d91838eccdc0e97a524800df92b7afb79 PLEASE CHANGE → graph theory PLEASE CHANGE → enhancement

New commits:

 ​7f3ef45 Added nice drawings for 4 graph families

### comment:3 Changed 2 years ago by Nina Klobas

Owner: set to Nina Klobas

### comment:4 Changed 2 years ago by Nina Klobas

Status: new → needs_review

### comment:5 Changed 2 years ago by David Coudert

Reviewers: → David Coudert needs_review → needs_work

Hello,

Thank you for contributing new graphs with nice embeddings.

Several improvements are needed in your code (which contains errors). I'm putting below a nicer and corrected version of method IGraph. Use it to improve the code of the other methods.

def IGraph(n, j, k):
r"""
Return an I-graph with 2n nodes.

The variables n, j, k are integers such that n > 2 and
0 < j, k \leq \lfloor (n - 1) / 2 \rfloor.
When j = 1 the resulting graph is isomorphic to the generalized Petersen
graph with the same n and k.

INPUT:

- n -- the number of nodes is 2 * n

- j -- integer 0 < j \leq \lfloor (n-1)/2 \rfloor. Decides how outer
vertices are connected.

- k -- integer 0 < k \leq \lfloor (n-1)/2 \rfloor. Decides how inner
vertices are connected.

PLOTTING: Upon construction, the position dictionary is filled to override
the spring-layout algorithm. By convention, the I-graphs are displayed as an
inner and outer cycle pair, with the first n nodes drawn on the outer
circle.  The first (0) node is drawn at the top of the outer-circle, moving
counterclockwise after that. The inner circle is drawn with the (n)th node
at the top, then counterclockwise as well.

EXAMPLES:

When j = 1 the resulting graph will be isomorphic to a generalized
Petersen graph::

sage: g = graphs.IGraph(7,1,2)
sage: g2 = GeneralizedPetersenGraph(7,2)
sage: g.is_isomorphic(g2)
True
"""
if n < 3:
raise ValueError("n must be larger than 2")
if j < 1 or j > (n - 1) // 2:
raise ValueError("j must be in 1 <= j <= floor((n - 1) / 2)")
if k < 1 or k > (n - 1) // 2:
raise ValueError("k must be in 1 <= k <= floor((n - 1) / 2)")

G = Graph(2 * n, name="I-graph (n={}, j={}, k={})".format(n, j, k))
for i in range(n):
G.add_edge(i, (i + j) % n)
G.add_edge(i + n, n + (i + k) % n)
return G


Could you also explain what is a IGraph ? For me this name is confusing since there is a graph library called igraph. Is it the most appropriate name ?

### comment:6 Changed 2 years ago by git

Commit: 7f3ef45d91838eccdc0e97a524800df92b7afb79 → d5b51a0369da31db3078e5b5352eda52f1f581c9

Branch pushed to git repo; I updated commit sha1. New commits:

 ​d5b51a0 Better structure of code

### comment:7 Changed 2 years ago by Nina Klobas

Regarding the definition of I-graphs one could check page 2 of the following paper.

### comment:8 Changed 2 years ago by David Coudert

You should add references to the definitions of these graphs. See e.g., #11736 for examples.

Also add a EXAMPLES: block to all methods.

### comment:10 Changed 2 years ago by Matthias Köppe

Milestone: sage-9.2 → sage-9.3

### comment:11 Changed 2 years ago by David Coudert

Branch: u/gh-NinaKl/drawing_generalizations_of_generalized_petersen_graphs → public/graphs/30728_drawings d5b51a0369da31db3078e5b5352eda52f1f581c9 → a2948cdcda637ba5a43646d53ba99afcb032fe44 needs_work → needs_review

I have rebased the branch on sage 9.3.beta5 performed several corrections / improvements. In particular, I have added missing references and updated some definitions to fit the original papers.

New commits:

 ​f60310c trac #30728: merge with 9.3.beta5 ​a2948cd trac #30728: review commit

### comment:12 Changed 2 years ago by git

Commit: a2948cdcda637ba5a43646d53ba99afcb032fe44 → 0d739ba082b679d266731e50e3709dbef5b1ee10

Branch pushed to git repo; I updated commit sha1. New commits:

 ​0d739ba trac #30728: fix block issue

### comment:13 Changed 2 years ago by David Coudert

For me this patch is now good to go, but a double check would be appreciated.

### comment:14 Changed 22 months ago by David Coudert

Status: needs_review → positive_review

I give this ticket a positive review. I did review edit to fix some issues and we have green bot since several weeks.

### comment:15 Changed 21 months ago by Volker Braun

Branch: public/graphs/30728_drawings → 0d739ba082b679d266731e50e3709dbef5b1ee10 → fixed positive_review → closed

### comment:16 Changed 21 months ago by Samuel Lelièvre

Commit: 0d739ba082b679d266731e50e3709dbef5b1ee10

Some "TESTS" blocks have a single colon : instead of double colon ::.

Please fix in follow-up ticket #31461.

Note: See TracTickets for help on using tickets.