A　container　shipping　network　connects　coastal　countries　with　each　other　and　facilitates　most　of　the　world　merchandise　trade.　Reliable　maritime　connectivity　ensures　the　availability　of　commodities　and　economic　growth.　The　global　spread　of　COVID-19　has　led　to　port　failures　and　service　cancellations,　resulting　in　decreased　connectivity　level　of　container　ports.　To　mitigate　the　impact　of　the　pandemic,　a　graph　theory　approach　is　proposed　to　strength　the　container　shipping　network　connectivity　by　considering　topology　and　the　possibility　of　opening　new　shipping　links　between　ports.　It　is　designed　to　maximize　network　connectivity　with　limited　addable　routes.　The　network　connectivity　is　measured　by　algebraic　connectivity,　and　the　possibility　of　opening　new　shipping　links　is　estimated　by　an　extended　gravity　model.　A　heuristic　algorithm　based　on　Fiedler　vector　is　introduced　to　obtain　the　optimal　solutions.　The　performance　of　the　proposed　model　and　algorithm　are　verified　by　testing　on　a　real-world　container　shipping　network　based　on　the　Alphaliner　database.　Experimental　results　illustrate　that　the　presented　model　is　efficient　and　effective　for　strengthening　the　connectivity.　Policy　makers　can　refer　to　the　suggested　optimal　shipping　links　to　facilitate　better　shipping　network　connectivity　in　the　context　of　the　COVID-19　pandemic.　©　2022　Elsevier　Ltd